text:
Designing efficient algorithms for difficult multi-objective optimization problems is a very challenging problem. In this paper a new clustering multi-objective evolutionary algorithm based on orthogonal and uniform design is proposed. First, the orthogonal design is used to generate initial population of points that are scattered uniformly over the feasible solution space, so that the algorithm can evenly scan the feasible solution space once to locate good points for further exploration in subsequent iterations. Second, to explore the search space efficiently and get uniformly distributed and widely spread solutions in objective space, a new crossover operator is designed. Its exploration focus is mainly put on the sparse part and the boundary part of the obtained non-dominated solutions in objective space. Third, to get desired number of well distributed solutions in objective space, a new clustering method is proposed to select the non-dominated solutions. Finally, experiments on thirteen very difficult benchmark problems were made, and the results indicate the proposed algorithm is efficient.
In the real world, many applications are non-stationary optimization problems. This requires that the optimization algorithms need to not only find the global optimal solution but also track the trajectory of the changing global best solution in a dynamic environment. To achieve this, this paper proposes a clustering particle swarm optimizer (CPSO) for dynamic optimization problems. The algorithm employs hierarchical clustering method to track multiple peaks based on a nearest neighbor search strategy. A fast local search method is also proposed to find the near optimal solutions in a local promising region in the search space. Six test problems generated from a generalized dynamic benchmark generator (GDBG) are used to test the performance of the proposed algorithm. The numerical experimental results show the efficiency of the proposed algorithm for dynamic optimization problems.
As a new research topic for reducing the number of function evaluations effectively in function optimization, an idea of utilizing a rough approximation model, which is an approximation model with low accuracy and without learning process, has been proposed. Although the approximation errors between true function values and their approximation values estimated by the rough approximation model are not small, the rough model can estimate the order relation of two points with fair accuracy. In order to use this feature of the rough model, we have proposed the estimated comparison method, which omits the function evaluations when the result of comparison can be judged by approximation values. In this study, kernel smoothers are adopted as rough approximation models. Various types of benchmark functions are solved by Differential Evolution (DE) with the estimated comparison method and the results are compared with those obtained by DE. It is shown that the estimated comparison method is general purpose method for reducing function evaluations and can work well with kernel smoothers. It is also shown that the potential model, which is a rough approximation model proposed by us, has better ability of function reduction than kernel smoothers.
This paper proposes a new variant of the PSO algorithm named Complex Neighborhood Particle Swarm Optimizer (CNPSO) for solving global optimization problems. In the CNPSO, the neighborhood of the particles is organized through a complex network which is modified during the search process. This evolution of the topology seeks to improve the influence of the most successful particles and it is fine tuned for maintaining the scale-free characteristics of the network while the optimization is being performed. The use of a scale-free topology instead of the usual regular or global neighborhoods is intended to bring to the search procedure a better capability of exploring promising regions without a premature convergence, which would result in the procedure being easily trapped in a local optimum. The performance of the CNPSO is compared with the standard PSO on some well-known and high-dimensional benchmark functions, ranging from multimodal to plateau-like problems. In all the cases the CNPSO outperformed the standard PSO.
A state-of-the-art problem in Computational Systems Biology is to provide suitable tools to model and predict the behaviour of multicellular systems (tissues, embryos) where biological interactions occur both inside and between cells (or compartments in general). Starting from existing computational models and languages such as stochastic pi-calculus, Petri Nets, mobile ambients, and membrane computing, we developed a new computational framework based on (i) a compositional model for biological compartments, and (ii) an enhanced model of chemical rules addressing also biomechanical actions such as substances diffusion across membranes or compartments splitting. We tested a fragment of the framework using a case study based on spatial pattern formation in embryogenesis, where the interplay between cells' internal dynamics and cell-to-cell interactions seems to have a central role.
Evolutionary algorithms have employed the SAW (Stepwise Adaptation of Weights) method in order to solve CSPs (Constraint Satisfaction Problems). This method originated in hill-climbing algorithms used to solve instances of 3-SAT by adapting a weight for each clause. Originally, adaptation of weights for solving CSPs was done by assigning a weight for each variable or each constraint. Here we investigate a SAW method which assigns a weight for each conflict. Two simple stochastic CSP solvers are presented. For both we show that constraint based SAW and conflict based SAW perform equally on easy CSP samples, but the conflict based SAW outperforms the constraint based SAW when applied to hard CSPs. Moreover, the best of the two suggested algorithms in its conflict based SAW version performs better than the best known evolutionary algorithm for CSPs that uses weight adaptation, and even better than the best known evolutionary algorithm for CSPs in general.
A cooperative coevolutionary algorithm (CCEA) is an extension to evolutionary algorithm (EA) which employs a divide and conquer strategy to solve an optimization problem. In its native form, a CCEA splits the variables of an optimization problem into multiple smaller subsets and evolves them independently in different subpopulations under a predefined collaborative scheme and a payoff strategy. The dynamics of CCEAs are far more complex than EAs and its performance can vary from good to bad depending on the separability of the problem. This paper provides some insights into why CCEAs in its native form is not be suitable for nonseparable problems and introduces a Cooperative Coevolutionary Algorithm with Correlation based Adaptive Variable Partitioning (CCEA-AVP) to deal with such problems. The performance of CCEA-AVP is compared with CCEA and an EA to highlight its benefits. CCEA-AVP offers the possibility to deal with problems where separability among variables might vary in different regions of the search space.
The Differential Evolution (DE) algorithm is a simple and efficient evolutionary algorithm that has been applied to solve many optimization problems mainly in continuous search domains. In the last few years, many implementations of multi-objective versions of DE have been proposed in the literature, combining the traditional differential mutation operator as the variation mechanism and some form of Pareto-ranking based fitness. In this paper, we propose the utilization of the differential mutation operator as an additional operator to be used within any multi-objective evolutionary algorithm that employs an archive (offline) population. The operator is applied for improving the high-quality solutions stored in the archive, working both as a local search operator and a diversity operator depending on the points selected to build the differential mutation. In order to illustrate the use of the operator, it is coupled with the NSGA-II and the multi-objective DE (MODE), showing promising results.
This paper investigates a distributed cellular Genetic Algorithm (dcGA) for the implementation of a GPS attitude determination system. Previously, a cellular GA architecture has been proposed considering several implementations; however, comparison among these reveals that accuracy is compromised when the population size is increased. In this paper, a distributed configuration approach is proposed and compared with previous implementations in the literature; a significant improvement in terms of accuracy is reported without increasing computational cost.
The genetic algorithm paradigm is a well-known heuristic for solving many problems in science and engineering. As problem sizes increase, a natural question is how to exploit advances in distributed and parallel computing to speed up the execution of genetic algorithms. This paper proposes a new distributed architecture for genetic algorithms, based on distributed storage of the individuals in a persistent pool. Processors extract individuals from the pool in order to perform the computations and then insert the resulting individuals back into the pool. Unlike previously proposed approaches, the new approach is tailored for distributed systems in which processors are loosely coupled, failure-prone and can run at different speeds. Proof-of-concept simulation results are presented indicating that the approach can deliver improved performance due to the distribution and tolerates a large fraction of crash failures.
Over the years, we have been applying multi-objective evolutionary algorithms (MOEAs) to a number of real-world problems. solving multi-objective optimization problems (MOOPs) in the real world faces a number of challenges including when to terminate the algorithm. This paper addresses this challenge by introducing what we call a 'stability measure'. We use this measure to estimate when to stop the multi-objective evolutionary search. For the proposed measure, the non-dominated set obtained by an MOEA will be tested under local variability in the decision variable space. A non-dominated solution found by the MOEA will be assigned a stability value, which corresponds to the number of solutions within the neighborhood that dominate it. Obviously, if the found non-dominated solution lies on the POF then there cannot be any such dominating solutions in its neighborhood. The average of quality values assigned to all non-dominated solutions will be used as the stability value for the set. In order to validate the proposed measure, we carried out measurements on the obtained non-dominated sets from four MOEAs including NSGA-II, SPEA2, hill-climber, and random-walk. We use random-walk in order to create a baseline for judging the performance of the algorithms, where we expect the highest level of variations to occur. To apply this measure at each generation, it incurs additional cost that does not contribute to the evolutionary search per se. This motivated us to add this measure as a local search operator. In this way, the local search operator plays two rules: (1) it attempts to find better solutions than the ones we have in the population; and (2) it acts as a stability measure for the evolutionary search. The results confirmed the usefulness of the proposed measure and algorithm.
In many real-world scenarios, in contrast to standard benchmark optimization problems, we may face some uncertainties regarding the objective function. One source of these uncertainties is a constantly changing environment in which the optima change their location over time. New heuristics or adaptations to already available algorithms must be conceived in order to deal with such problems. Among the desirable features that a search strategy should exhibit to deal with dynamic optimization are diversity maintenance, a memory of past solutions, and a multipopulation structure of candidate solutions. In this paper, an immune-inspired algorithm that presents these features, called dopt-aiNet, is properly adapted to deal with six newly proposed benchmark instances, and the obtained results are outlined according to the available specifications for the competition at the Congress on Evolutionary Computation 2009.
The increasing in the demand for Wireless Sensor Networks (WSNs) has intensified studies which aim to obtain energy-efficient solutions, since the energy storage limitation is critical in those systems. However, there are other aspects which usually must be ensured in order to provide an efficient design of WSNs, such as area coverage and network connectivity. This paper proposes a multiobjective hybrid approach for solving the Dynamic Coverage and Connectivity Problem (DCCP) in flat WSN subjected to node failures. It combines a multiobjective global on-demand algorithm (MGoDA), which improves the current DCCP solution using a Genetic Algorithm, with a local online algorithm (LoA), which is intended to restore the network coverage when one or more failures occur. The proposed approach is compared with an Integer Linear Programming (ILP) based approach and a similar mono-objective approach with regard to coverage, energy consumption and residual energy of the solution provided by each method. Results achieved for a test instance show that the hybrid approach presented can obtain good solutions with a considerably smaller computational cost than ILP. The multiobjective approach still provides a feasible method for extending WSNs lifetime with slight decreasing in the network mean coverage.
In this paper we propose a generalized formulation of the evolutionary heuristic governing the movement of the individuals of Differential Evolution in the search space. The basic heuristic of Differential Evolution is casted in form of discrete dynamical system and extended to improve local convergence. It is demonstrated that under some assumption on the local structure of the objective function, the proposed dynamical system, has fixed points towards which it converges asymptotically. This property is used to derive an algorithm that performs better than standard Differential Evolution on some space trajectory optimization problems. The novel algorithm is then extended with a global restart procedure that further increases the performance reducing the probability of stagnation in deceptive local minima.
We present a new penalty-based genetic algorithm for the multi-source and multi-sink minimum vertex cut problem, and illustrate the algorithm's usefulness with two real-world applications. It is proved in this paper that the genetic algorithm always produces a feasible solution by exploiting some domain-specific knowledge. The genetic algorithm has been implemented on the example applications and evaluated to show how well it scales as the problem size increases.
In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of 'hard' exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.
This paper presents a harmony search algorithm with ensemble of parameter sets, named EHS algorithm, for solving continuous optimization problems. In the proposed algorithm, an ensemble of parameter sets is adopted to self-adaptively choose the best control parameters during the evolution process. This method not only eliminates the need to perform the trail-and-error search for the best single parameter set, but enables us to benefit from the match between the parameter sets, the different search phases, and the specific problems as well. Extensive computational simulations and comparisons are carried out by employing a set of 10 benchmark problems from the literature. The computational results show that the proposed EHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants [1,2,3].
Prioritisation is an important technique for resolving planning conflicts between agents with shared resources, such as robots moving through a shared space. This paper explores the use of genetic-based machine learning to assign priority dynamically, to improve performance of a team of agents without unduly impacting individual agents' performance. A decoupled heuristic approach is used for flexibility, whereby individual XCS agents learn to optimise their behaviour first, and then a high-level planner agent is introduced and trained to resolve conflicts by assigning priority. The approach is designed for Partially Observable Markov Decision Process (POMDP) environments and demonstrated on a problem in 3D aircraft path planning.
A cellular automaton (CA) has been used in pseudorandom number generation (PRNG) for over a decade. Some studies show that conventional one-dimensional (1-D) CA PRNG can not generate perfect pseudorandom number sequences while 2-D CA PRNG is too complex though it can produce high quality random numbers. In this paper, a novel structure PRNG is proposed which called twi-layer couple cellular automata (TLCCA). Each layer in TLCCA is divided into two parts and two methods are adopted to couple with the two parts in lower layer and upper layer. In lower layer, two parts select their own rules while a couple neighborhood is adopted in upper layer. The merit of TLCCA PRNG is it can produce high quality random number with a relatively simple structure. The results of experiment also indicate TLCCA PRNG has a higher efficiency and better robusticity.
This paper describes a new technique for training microwave neural network models. The proposed technique combines quasi-Newton algorithm with a global optimization algorithm called Particle Swarm Optimization (PSO). The quasi-Newton process for searching optimal solutions is incorporated into PSO to speed up local search, while the PSO performs global search avoid being trapped in local minima of training. The overall algorithm iterates between quasi-Newton and PSO. Neural network training for microwave circuit modeling, such as waveguide and microstrip examples is presented, demonstrating that the proposed algorithm achieves more accurate models than the conventional gradient based technique and the conventional PSOs.
In this paper we describe the application of a Hybrid Grouping Genetic Algorithm (HGGA) to the recent challenge of deploying metropolitan wireless networks, exploiting existing broadband infrastructure, by opening WiFi-enabled customers' DSL routers to third parties, or WiFi network Design Problem or WiFiDP. The application of a HGGA to this problem aims to produce the layout of a cost effective network deployment plan, considering real life aspects such as budget and DSL router characteristics (coverage, DSL capacity at a specific location, unit price, etc.) The total cost of deployment (i.e. the cost of opening all selected DSL routers for public use) should not exceed the allocated budget. The hybrid groping genetic algorithm proposed includes a specific encoding to tackle the WiFiDP, in which the group part also includes the type of router to be installed. Moreover, a repairing and local search procedures are included in the algorithm to obtain better performance and always finding feasible solutions. The performance and effectiveness of the proposed HGGA is evaluated using two randomly generated WiFiDP instances (considering 1000 and 2000 users) that were used to perform several experiments. From theses datasets, we compare the results of the proposed HGGA with that of a greedy optimization algorithm previously proposed to solve the WiFiDP challenge.
The Probabilistic Traveling Salesman Problem is a variation of the classic Traveling Salesman Problem and one of the most significant stochastic routing problems. In this paper, a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization (HBMO), Greedy Randomized Adaptive Search Procedure (GRASP) and Expanding Neighborhood Search Strategy (ENS) is proposed for the solution of the Probabilistic Traveling Salesman Problem. The proposed algorithm has two additional main innovative features compared to other Honey Bees Mating Optimization algorithms that concern the crossover operator and the workers. The proposed algorithm is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm, the Particle Swarm Optimization (PSO) algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in 6 out of 10 cases the proposed algorithm gives a new best solution.
This article describes a hybrid multiple populations based evolutionary approach for disjunctive mathematical programs with uncertainties in the problem data. The problems are formulated as two-stage linear disjunctive programming problems which are solved by a stage decomposition based hybrid algorithm using multiple evolutionary algorithms to handle the disjunctive sets of the here-and-now (first stage) decisions and mathematical programming to handle the recourse (second stage) decisions. By an appropriate representation of the first-stage disjunctive solution space, the overall problem is decomposed into smaller subproblems without disjunctions. The resulting decomposed first-stage subproblems are solved independently by evolutionary algorithms, leading to parallel evolutions based on multiple populations. During the progress of the optimization, the number of subproblems is systematically reduced by comparing the current best global solution (upper bound) to lower bounds for the subproblems. This approach guaranties that the global optimal solution remains in the union of solution spaces of the remaining subproblems. A comparison of a classical evolutionary algorithm and the new multiple populations evolutionary algorithm for a real world batch scheduling problem shows that the new approach leads to a significantly improved coverage of the set of feasible solutions such that high quality feasible solutions can be generated faster.
Global optimization problems with numerous local and global optima are difficult to solve, which can trap traditional genetic algorithms. To solve the problems, a hybrid self-adaptive genetic algorithm based on sexual reproduction and Baldwin effect is presented for global optimization in this paper. By simulating sexual reproduction in nature, the proposed algorithm utilizes a gender determination method to determine the gender of individuals in population. Then, it adopts the different initial genetic parameters for female and male subgroups, and self-adaptively adjusts the sexual genetic operation based on the competition and cooperation between different gender subgroups. Furthermore, the fitness information transmission between parents and offspring is implemented to guide the evolution of individuals' acquired fitness. Moreover, on the basis of the Darwinian evolution theory, the proposed algorithm guides individuals to forward or reverse acquired reinforcement learning based on Baldwin effect in niche. Numerical simulations are conducted for a set of benchmark functions with different dimensional decision variables. The results show that the proposed algorithm can find optimal or closer-to-optimal solution, and has faster search speed and higher convergence rate.
A large normal displacement relative to the ecliptic is necessary for mitigating the effect of the zodiacal dust cloud on space telescopes. In this paper, a memetic algorithm is used to optimize flyby paths using multiple gravity-assisted maneuvers near Earth (E) and Venus (V), which are used for reaching Jupiter (J), where the inclination is increased. The global search for optimal trajectories with minimal energy requirements and short transfer times to the highly-inclined destination orbit is performed using a niching genetic algorithm improved by a gradient-based local optimization. The optimization yields three candidate paths: EVEJ, EVEEJ and EVVEJ.
A novel memory-based particle swarm optimization algorithm employing externally implemented global (shared) and particle-based (local) memories and a colonization approach similar to artificial immune system algorithms is presented. At any iteration, particle-based memories keep a number of previously best performing personal positions for each particle and the global memory keeps a number of globally best positions found so far. A set of velocities is computed for each particle using each of the personal best positions within its local memory and a number of randomly selected positions from the global memory. This way, a colony of new positions is obtained for each particle and the one with the best fitness is selected and put within the new swarm. Global and local memories are also updated using the solutions within each colony. This new memory-based strategy is used for the solution of problems within the CEC2005 test suit. Experimental evaluations demonstrated that the proposed strategy outperformed the conventional and other known memory-based PSO algorithms for all problem instances.
Differential evolution is used to search the parameter space of a system of ordinary differential equations (ODEs). For each tested parameter set, one time series resulting from integration of the ODE system is used to drive a dynamic system of interest. A fitness function is designed such that the response of the driven system is forced to have properties that are desirable to the practitioner. The dynamic versatility of a nonlinear ODE system coupled with an evolutionary algorithm search of its parameter space allows for significant improvement in excitation fitness. The input tailoring technique is generally applicable to a number of problems and is shown in this work to generate a chaotic modulation that reduces the power required to disrupt normal operation of a phase-locked loop.
A model for intrinsic artificial development is introduced in this paper. The proposed model features a novel mechanism where growth emerges, rather than being triggered by a single action. Different types of cell signalling ensure that breaking symmetries is rather the norm than an exception, and gene activity is regulated on two layers: first, by the proteins that are produced by the gene regulatory network (GRN). Second, through structural feedback by second messenger molecules, which are not directly produced through gene expression, but are produced by sensor proteins, which take the cell's structure into account. The latter feedback mechanism is a novel approach, intended to enable adaptivity and environment coupling in real-world applications. The model is implemented in hardware, and is designed to run autonomously in resource limited embedded systems. Initial experiments are carried out to measure long-term stability, dynamics, adaptivity and scalability of the new approach. Furthermore the ability of the GRN to produce patterns of different symmetries is examined.
The immune system is a key component in the maintenance of host homeostasis. Key actors in this process are cells known as dendritic cells (DCs). An Artificial Immune System based on DCs (known as the Dendritic Cell Algorithm: DCA) is well established in the literature and has been applied in a number of applications. Work in this paper is concerned with the development of an integrated homeostatic system for small, autonomous robotic systems, implemented on a resource limited micro-controller. As a first step, we have modified the DCA to operate in both simulated robotic units, and a resource constrained micro-controller that can operate in an on-line manner. Errors can be introduced into the robotic unit during operation, and these can be detected and then circumvented by the modified DCA.
In this paper, a new mechanism for dynamically varying the population size is proposed based on a previously modified PSO algorithm (nPSO). This new algorithm is extended to the multi-objective optimisation case by applying the Random Weighted Aggregation (RWA) technique and by maintaining an archive for preserving the suitable Pareto-optimal solutions. Both the single objective and multi-objective optimisation algorithms were tested using well-known benchmark problems. The results show that the proposed algorithms outperform some of the other salient Evolutionary Algorithms (EAs). The proposed algorithms were further applied successfully to the optimal design problem of alloy steels, which aims at determining the optimal heat treatment regime and the required weight percentages for chemical composites to obtain the desired mechanical properties of steel hence minimising production costs and achieving the overarching aim of 'right-first-time production' of metals.
Multicasting routing is an effective way to communicate among multiple hosts in computer networks. Usually multiple quality of service (QoS) guarantees are required in most of multicast applications. Several researchers have investigated genetic algorithms-based models for multicast route computation with QoS requirements. The evolutionary models proposed here use multi-objective approaches in a Pareto sense to solve this problem and to deal with the inheriting multiple metrics involved in QoS proposal. Basically, we construct three QoS-constrained multicasting routing algorithms; the first one was based on NSGA, the second one was based on NSGA-II and the third is an adaptation of NSGAII incorporating the concept of ε-dominance. These algorithms were applied to find multicast routes over two network topologies. Three different pairs of objectives were evaluated; the first objective used in each pair is related to the total cost of a multicast route and the second metric is related to delay. The first evaluated delay metric computes the total delay involved in the tree solution; the second one computes the mean delay accumulated from the source to each destination node; the third one is the maximum delay accumulated from the source to a destination node. Our results indicated that the NSGA-II environment incorporating the concept of ε-dominance – named ε-NSGA-II multicasting routing - returned the best performance.
The Redundancy Allocation Problem (RAP) is a kind of reliability optimization problems. It involves the selection of components with appropriate levels of redundancy or reliability to maximize the system reliability under some predefined constraints. We can formulate the RAP as a combinatorial problem when just considering the redundancy level, while as a continuous problem when considering the reliability level. The RAP employed in this paper is that kind of combinatorial optimization problems. During the past thirty years, there have already been a number of investigations on RAP. However, these investigations often treat RAP as a single objective problem with the only goal to maximize the system reliability (or minimize the designing cost). In this paper, we regard RAP as a multi-objective optimization problem: the reliability of the system and the corresponding designing cost are considered as two different objectives. Consequently, we can utilize a classical Multi-objective Evolutionary Algorithm (MOEA), named Non-dominated Sorting Genetic Algorithm II (NSGA-II), to cope with this multi-objective redundancy allocation problem (MORAP) under a number of constraints. The experimental results demonstrate that the multi-objective evolutionary approach can provide more promising solutions in comparison with two widely used single-objective approaches on two parallel-series systems which are frequently studied in the field of reliability optimization.
This work describes a biologically inspired system for the coordination of multiple and possibly conflicting behaviours in an autonomous mobile robot, devoted to exploring novel environments while maintaining coherent internal dynamics. The Evolutionary Artificial Homeostatic System, derived from knowledge of how organisms self-regulates in order to keep their essential variables within a limited range (homeostasis), is composed of an artificial endocrine system, including two hormones and two hormone receptors, and also three previously evolved NSGasNet artificial neural networks. It is shown that the integration of receptors enhances the system robustness without the need for additional a priori knowledge being incorporated into the three evolved NSGasNets. The experiments conducted also show that the proposed multihormone evolutionary artificial homeostatic system is able to successfully coordinate a multiple and conflicting behaviours task, being also robust enough to cope with internal and external disruptions.
Abstract—An improved Differential Evolution (DE) that incorporates a wavelet-based mutation operation to control the scaling factor is proposed. The wavelet theory applied is to enhance DE in exploring the solution spaces more effectively for better solutions. A suite of benchmark test functions is employed to evaluate the performance of the proposed method. It is shown empirically that the proposed method outperforms significantly the existing methods in terms of convergence speed, solution quality and solution stability.
In this paper, we propose a new selection criterion for candidate solutions to a constrained optimization problem. Such a selection mechanism is incorporated into a differential evolution (DE) algorithm. This DE approach is then hybridized with an operator based on the Nelder-Mead method, whose aim is to speed up convergence towards good solutions. The proposed approach is called "Hybrid of Differential Evolution and the Simplex Method for Constrained Optimization Problems" (HDESMCO), and is validated using a well-know benchmark for constrained evolutionary optimization. The results indicate that our proposed approach produces solutions whose quality is competitive with respect to those generated by three evolutionary algorithms from the state-of-the-art (improved stochastic ranking, diversity-DE and Generalized Differential Evolution), but requiring a lower number of objective function evaluations.
The purpose of this paper is to propose a new real-coded genetic algorithm (RCGA) named Networked Genetic Algorithm (NGA) that intends to find multiple optima simultaneously in deceptive globally multimodal landscapes. Most current techniques such as niching for finding multiple optima take account of big valley landscapes or non-deceptive globally multimodal landscapes but not deceptive ones called UV-landscapes. Adaptive Neighboring Search (ANS) is a promising approach for finding multiple optima in UV-landscapes. ANS utilizes a restricted mating scheme with a crossover-like mutation in order to find optima in deceptive globally multimodal landscapes. However, ANS has a fundamental problem that it does not find all the optima simultaneously in many cases. NGA overcomes the problem by an adaptive parent-selection scheme and an improved crossover-like mutation. We show the effectiveness of NGA over ANS in terms of the number of detected optima in a single run on Fletcher and Powell functions as benchmark problems that are known to have UV-landscapes. We also analyze the behavior of NGA to confirm that the adaptive parent-selection scheme contributes performance of NGA.
The process of creating e-learning contents using reusable learning objects (LOs) can be broken down in two sub-processes: LOs finding and LO sequencing. Sequencing is usually performed by instructors, who create courses targeting generic profiles rather than personalized materials. This paper proposes an evolutionary approach to automate this latter problem while, simultaneously, encourages reusability and interoperability by promoting standards employment. A model that enables automated curriculum sequencing is proposed. By means of interoperable competency records and LO metadata, the sequencing problem is turned into a constraint satisfaction problem. Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) agents are designed, built and tested in real and simulated scenarios. Results show both approaches succeed in all test cases, and that they handle reasonably computational complexity inherent to this problem, but PSO approach outperforms GA.
In our previous work we have proposed an ant colony optimization (ACO) algorithm for feature selection. In this paper we hybridize the algorithm with a genetic algorithm (GA) to obtain excellent features of two algorithms by synthesizing them. Proposed algorithm is applied to a challenging feature selection problem. This is a data mining problem involving the categorization of text documents. We report the extensive comparison between our proposed algorithm and three existing algorithms – ACO-based, information gain (IG) and CHI algorithms proposed in the literature. Proposed algorithm is easily implemented and because of use of a simple classifier in that, its computational complexity is very low. Experimentations are carried out on Reuters-21578 dataset. Simulation results on Reuters-21578 dataset show the superiority of the proposed algorithm.
The protein structure prediction (PSP) problem is one of the most important problems in computational biology. This paper proposes a novel Estimation of Distribution Algorithms (EDAs) based method to solve the PSP problem on HP model. Firstly, a composite fitness function containing the information of folding structure core formation is introduced to replace the traditional fitness function of HP model. It can help to select more optimum individuals for probabilistic model in each iteration of EDAs algorithm. And a set of guided mutation operators are used to increase the diversity of population and the likelihood of escaping from local optima. Secondly, an improved backtracking repairing algorithm is proposed to repair invalid individuals sampled by the probabilistic model of EDAs for the long sequence protein instances. The improved algorithm adds a detection procedure to avoid entering invalid closed areas when selecting directions for the residues. Therefore, it can sharply reduce the number of backtracking operation and the computational cost for long sequence protein. Experimental results demonstrate that the proposed method outperform the basic EDAs method. At the same time, it is very competitive with the other existing algorithms for the PSP problem on lattice HP models.
Evolutionary Algorithms are amongst the best known methods of solving difficult constraint optimization problems, for which traditional methods are not applicable. However, there are no inbuilt or organic mechanisms available in Evolutionary Algorithms for handling constraints in optimization problems. These problems are solved by converting or treating them as unconstrained optimization problems. Several constraint handling techniques have been developed and reported in literature, of which, the penalty factor and feasibility rules are the most promising and widely used for such purposes. However, each of these techniques has its own advantages and disadvantages and often require fine tuning of one or more parameters, which in itself becomes an optimization problem. This paper presents a hybrid constraint handling technique for a two population adaptive co-evolutionary algorithm, which uses a self determining and regulating penalty factor method as well as feasibility rules for handling constraints. Thus, the method overcomes the drawbacks in both the methods and utilizes their strengths to effectively and efficiently handle constraints. The simulation on ten benchmark problems demonstrates the efficacy of the approach.
In this paper, we present a description of our research in the field of data mining. We describe a two level hybrid evolutionary approach for classification rule extraction. Our method is a mix of two classic approaches called respectively Michigan and Pittsburg approaches. The goal is to take advantage of both approaches while minimising their drawbacks. The result has been compared favourably to classical approaches.
This paper proposes a parallel evolutionary algorithm to tackle the Fully Interconnected Network Design Problem (FINDP), a specific application of hub location to network design. The FINDP has been recently proposed as an NP-hard combinatorial optimization problem formed by two smaller sub-problems: first, given the nodes which form the network, classify them as belonging to the backbone network or not. The second sub-problem consists of assigning the access network to a hub (node of the backbone network). In this paper we propose a parallel evolutionary algorithm to tackle the FINDP. We describe the architecture and how to structure the algorithm to solve the problem. Experimental tests have been carried out in several synthetic instances, and a comparison with existing approaches have shown the good performance of our algorithm.
This work presents a methodology for the application of a parallel genetic algorithm (PGA) to the problem of protein folding prediction, using the 3DHP-Side Chain model. This model is more realistic than the usual 3DHP model but, on the other hand, it is has a higher degree of complexity. Specific encoding and fitness function were proposed for this model, and running parameters were experimentally set for the standard master-slave PGA. The system was tested with a benchmark of synthetic sequences, obtaining good results. An analysis of performance of the parallel implementation was done, compared with the sequential version. Overall results suggest that the approach is efficient and promising.
This paper presents the Hierarchical Cluster Counting (HCC), a new quality metric for nondominated sets generated by multi-objective optimizers that is based on hierarchical clustering techniques. In the computation of the HCC, the samples in the estimate set are sequentially grouped into clusters. The nearest clusters in a given iteration are joined together until all the data is grouped in only one class. The distances of fusion used at each iteration of the hierarchical agglomerative clustering process are integrated into one value, which is the value of the HCC for that estimate set. The examples show that the HCC metric is able to evaluate both the extension and uniformity of the samples in the estimate set, making it suitable as a unary diversity metric for multiobjective optimization.
In this paper we shall present a reconfigurable architecture that has been specifically conceived for emulating large-scale bio-inspired systems. The architecture is organized as a regular array of programmable elements that can be used either as fine grain logic elements or configured in order to construct massively parallel SIMD (Single Instruction Multiple Data) machines. As it will be explained, the specific features that have been included in the architecture permit the efficient implementation of a wide range of complex systems.
A gene regulatory network describes the influence of genes over others. This paper attempts to model gene regulatory network by a recurrent neural net with fuzzy membership distribution of weights. A cost function is designed to match the response of neurons in the network with the gene expression data, and a differential evolution algorithm is used to minimize the cost function. The minimization yields fuzzy membership distribution of weights, which on de-fuzzification provides the desired signed weights of the gene regulatory network. Computer simulation reveals that the proposed method outperforms existing techniques in detecting sign, and magnitude of weights of the regulatory network.
Since the Gate Assignment Problem (GAP) at airport terminals is a combinatorial optimization problem, permutation representations based on aircraft dwelling orders are usually used in the implementations of Genetic Algorithms (GAs), and the design of such GAs is often confronted with feasibility problems and memory-efficiency problems. This paper proposes a hybrid GA, which transforms the original order based GAP solutions into value based ones, so that the basic binary representation and all classic evolutionary operations can apply free of the above problems. In the hybrid GA scheme, aircraft queues to gates are projected as points into a parameterized space, a deterministic model inspired by the natural ripple-spreading phenomenon is developed which uses relative spatial parameters as input to connect all aircraft points to form some aircraft queues to gates, and then a traditional binary GA compatible to all classic evolutionary operators is used to evolve these spatial parameters in order to find an optimal or near-optimal solution. The effectiveness of the new hybrid GA based on the ripple-spreading model for the GAP problem are illustrated by experiments.
This paper proposed Self-Guided genetic algorithm, which is one of the algorithms in the category of evolutionary algorithm based on probabilistic models (EAPM), to solve strong NP-Hard flowshop scheduling problems with the minimization of makespan. Most EAPM research explicitly used the probabilistic model from the parental distribution, then generated solutions by sampling from the probabilistic model without using genetic operators. Although EAPM is promising in solving different kinds of problems, Self-Guided GA doesn't intend to generate solution by the probabilistic model directly because the time-complexity is high when we solve combinatorial problems, particularly the sequencing ones. As a result, the probabilistic model serves as a fitness surrogate which estimates the fitness of the new solution beforehand in this research. So the probabilistic model is used to guide the evolutionary process of crossover and mutation. This research studied the flowshop scheduling problems and the corresponding experiment were conducted. From the results, it shows that the Self-Guided GA outperformed other algorithms significantly. In addition, Self-Guided GA works more efficiently than previous EAPM. As a result, Self-Guided GA is promising in solving the flowshop scheduling problems.
In order to find a satisfactory solution, genetic algorithms, in spite of their ability to solve difficult optimization problems, usually require a large number of fitness evaluations. When expensive simulations are required, using genetic algorithms as optimization tools can become prohibitive. In this paper we present a strategy for introducing surrogate models into genetic algorithms in order to enhance the quality of the final results, where a fixed budget of simulations is imposed. In this strategy, only a fraction of the population is evaluated by the exact function, thus allowing for more generations to evolve the population. The results obtained indicate that the proposed framework arises as an attractive alternative to improve the performance of the genetic algorithm within a fixed budget of expensive fitness evaluations.
The urban transit routing problem (UTRP) for public transport systems involves finding a set of efficient transit routes to meet customer demands. The UTRP is an NP-Hard, highly constrained, multi-objective problem, for which the evaluation of candidate route sets can prove both time consuming and challenging, with many potential solutions rejected on the grounds of infeasibility. In this paper we propose a simple evolutionary multi-objective optimization technique to solve the UTRP. First we present a representation of the UTRP and introduce our two key objectives, which are to minimise both passenger costs and operator costs. Following this, we describe a simple multi-objective optimization algorithm for the UTRP then present experimental results obtained using the Mandl's benchmark data and a larger transport network.
Differentiation Evolution (DE) is an Evolutionary Algorithm (EA) for solving function optimization problems. In order to renew the population in EA, there are two generation models. The first one is 'discrete generation model', and the second one is 'continuous generation model'. Conventional DEs have been based on the discrete generation model in which the current generation's population is replaced by the next generation's population at a time. In this paper, a novel DE based on the continuous generation model is proposed. Because a newborn excellent individual is added to an only population and can be used immediately to generate offspring in the continuous generation model, it can be expected that the novel DE converges faster than the conventional ones. Furthermore, by employing the continuous generation model, it becomes easy to introduce various survival selection methods into DE. Therefore, three survival selection methods are contrived for the DE based on the continuous generation model. Finally, the effects of the generation model, the survival selection method, the reproduction selection method, the population size and their interactions on the performance of DE are evaluated statistically by using the analysis of variance (ANOVA).
The fast evolutionary programming (FEP) introduced the Cauchy distribution into its mutation operator, thus the performances of EP were promoted significantly on a number of benchmark problems. However, the scaling parameter of the Cauchy mutation is invariable, which has become an obstacle for FEP to reach better performance. This paper proposes and analyzes a new stochastic method for controlling the variable scaling parameters of Cauchy mutation. This stochastic method collects information from a group of individuals randomly selected from the population. Empirical evidence validates our method to be very helpful in promoting the performance of FEP.
We study empirically the effects of operator and parameter choices on the performance of the non-revisiting genetic algorithm (NrGA). For a suite of 14 benchmark functions that include both uni-modal and multi-modal functions, it is found that NrGA is insensitive to the axis resolution of the problem, which is a good feature. From the empirical experiments, for operators, it is found that crossover is an essential operator for NrGA, and the best crossover operator is uniform crossover, while the best selection operator is elitist selection. For parameters, a small population, with a population size strictly larger than 1, should be used; the performance is monotonically increasing with crossover rate and the optimal crossover rate is 0.5. The results of this paper provide empirical guidelines for operator designs and parameter settings of NrGA.
In this paper, we propose a Subproblem-dependent Heuristic (SH) for MOEA/D to deal with the Deployment and Power Assignment Problem (DPAP) in Wireless Sensor Networks (WSNs). The goal of the DPAP is to assign locations and transmit power levels to sensor nodes for maximizing the network coverage and lifetime objectives. In our method, the DPAP is decomposed into a number of scalar subproblems. The subproblems are optimized in parallel, by using neighborhood information and problem-specific knowledge. The proposed SH probabilistically alternates between two DPAP-specific strategies based on the subproblems objective preferences. Simulation results have shown that MOEA/D performs better than NSGA-II in several WSN instances.
This paper presents a novel differential evolution algorithm based on variable neighborhood search to solve real-parameter continuous function optimization problems. In order to provide differential evolution algorithm with local intensification capability, each trial individual is generated by a variable neighborhood search algorithm using variable mutation and crossover probabilities. The novelty stems from the fact that while a pure differential evolution algorithm achieves global exploration during the search process, variable neighborhood search algorithm intensifies the search around local minima by using traditional DE mutation and crossover operators. The algorithm was tested using benchmark instances designed for a special session in CEC05. The experimental results show its highly competitive performance against its traditional counterpart as well as against the differential evolution with local search by Noman and Iba in [1] (IEEE Transaction on Evolutionary Computation, Vol. 12, No. 1, pp. 107-125, February 2008).
A cognitive system is presented, which is based on coupling a multi-objective evolutionary algorithm with a fuzzy information processing system. The aim of the system is to identify optimal solutions for multiple criteria that involve linguistic concepts, and to systematically identify a most suitable solution among the alternatives. The cognitive features are formed by the integration of fuzzy information processing for knowledge representation and evolutionary multi-objective optimization resulting in a decision-making outcome among several equally valid options. Cognition is defined as final decision-making based not exclusively on optimization outcomes but also some higher-order aspects, which do not play role in the pure optimization process. By doing so, the decisions are not merely subject to rationales of the computations but they are the resolutions with the presence of environmental considerations integrated into the computations. The work describes a novel fuzzy system structure serving for this purpose and a novel evolutionary multi-objective optimization strategy for effective Pareto-front formation serving for the goal. The machine cognition is exemplified by means of a design example, where a number of objects are optimally placed according to a number of architectural criteria.
Computational modeling of natural systems can be used for interdisciplinary applications, such as the configuration of robotic systems or the validation of biological ones. Up to date there has been a little progress on suggesting a framework for automating the process of creating a computational model for biological processes. Instead researchers focus on the implementations of systems that are intended to replicate a tight set of biological behaviors. Such framework should be able to construct any system based on the appropriate level of abstraction chosen by the designer, as well as be able to enforce the appropriate biological consistency without compromising on performance or scalability of the generated models. In this paper we propose a framework that can automate the construction of computational models using genetic algorithms and demonstrate how this framework can construct a model of the parieto-frontal and premotor regions involved in grasping.
Distribution Estimation Using Markov network (DEUM) algorithm is a class of estimation of distribution algorithms that uses Markov networks to model and sample the distribution. Several different versions of this algorithm have been proposed and are shown to work well in a number of different optimisation problems. One of the key similarities between all of the DEUM algorithms proposed so far is that they all assume the interaction between variables in the problem to be pre given. In other words, they do not learn the structure of the problem and assume that it is known in advance. Therefore, they may not be classified as full estimation of distribution algorithms. This work presents a fully multivariate DEUM algorithm that can automatically learn the undirected structure of the problem, automatically find the cliques from the structure and automatically estimate a joint probability model of the Markov network. This model is then sampled using Monte Carlo samplers. The proposed DEUM algorithm can be applied to any general optimisation problem even when the structure is not known.
An effective particle swarm - quasi-Newton hybrid for the optimisation of continuous functions is developed, which is shown to work well on a range of test problems. This method exploits the global exploration abilities of the PSO algorithm and the fast convergence of the quasi-Newton method. New switching heuristics between the quasi-Newton and PSO methods are introduced, with the update pairs being used to generate new particles. The new hybrid, called L-PSO, is shown to be effective in obtaining the global minimum on a range of test problems, and outperforms previous hybrids with which it is compared.
Ant Colony Optimization (ACO) is a metaheuristic method that inspired by the behavior of real ant colonies. In this paper, we propose a hybrid ACO algorithm for solving vehicle routing problem (VRP) heuristically in combination with an exact Algorithm to improve both the performance of the algorithm and the quality of solutions. In the basic VRP, geographically scattered customers of known demand are supplied from a single depot by a fleet of identically capacitated vehicles which are subject to architecture weight limit and, in some cases, to a limit on the distance traveled. Only one vehicle is allowed to supply each customer. The objective is to design least cost routes for the vehicles to service the customers. The intuition of the proposed algorithm is that nodes which are near to each other will probably belong to the same branch of the minimum spanning tree of the problem graph and thus will probably belong to the same route in VRP. In the proposed algorithm, in each iteration, we first apply a modified implementation of Prim's algorithm to the graph of the problem to obtain a feasible minimum spanning tree (MST) solution. Given a clustering of client nodes, the solution is to find a route in these clusters by using ACO with a modified version of transition rule of the ants. At the end of each iteration, ACO tries to improve the quality of solutions by using a local search algorithm, and update the associated weights of the graph arcs.
Engineering optimization often deals with very large search spaces which are highly constrained by nonlinear equations that restrict the values of the continuous variables. In this contribution the development of a memetic algorithm (MA) for global optimization in the solution of a problem in the chemical process engineering domain is described. The combination of an evolutionary strategy and a local solver based on the general reduced gradient method enables the exploitation of a significant reduction in the search space and of the ability of local mathematical programming solvers to efficiently handle large continuous problems containing equality constraints. The global performance of the MA is improved by the exclusion of regions that are defined by approximations of the basins of attraction of the local optima. The MA is compared to the combination of a scatter search based multi-start heuristic using OQNLP and the local solver CONOPT.
A haplotype is a DNA sequence that is inherited from one parent. They are especially important in the study of complex diseases since they contain more information than genotype data, so the next high priority in human genomics will involve the development of a full Haplotype Map of human genome [1]. However, obtaining haplotype data is technically difficult and expensive. One of the computational methods for getting haplotype data from genotype data is the pure parsimony criterion, an approach known as Haplotype Inference by Pure Parsimony (HIPP). It has been proved to be an NP-hard problem. We present a new preprocessing method which drastically decreases the number of relevant haplotypes. Several algorithms need to preprocess data; for big problem instances this key procedure is even more important than the process. This preprocessing was eventually tested on real and simulated data applying a tabu search, and the performance of the resulting algorithm showed it to be competitive with the best actual solvers.
Constructive Induction (CI) is a process applied to representation space prior to learning algorithms. This process transforms original representation space into a representation that highlights regularities. In this new improved space learning algorithms work more effectively, generating better solutions. Most CI methods apply a greedy strategy to improve representation space. Greedy methods might converge to local optima, when search space is complex. Genetic Algorithms (GA) as a global search strategy is more effective in such situations. In this paper, a real-coded GA (RGACI) model is represented for CI. This model optimizes the representation space by discretization of feature's values, constructing new features with a GA and evaluation and selection of features upon a PNN Classifier accuracy. Results reveal that PNN Classifier accuracy will improved considerably after it is integrated with RGACI model.
The ever increasing popularity of particle swarm optimization (PSO) algorithm is recently attracting attention to the embedded computing world. Although PSO is in general considered to be computationally efficient algorithm, its direct software implementation on complex problems, targeted on low capacity embedded processors could however suffer from poor execution performance. This paper first evaluates the performance of the standard PSO algorithm on a typical embedded platform (using a 16-bit microcontroller). Then, a modular, flexible and reusable architecture for a hardware PSO engine, for accelerating the algorithm's performance, will be presented. Finally, implementation test results of the proposed architecture targeted on Field Programmable Gate Array (FPGA) technology will be presented and its performance compared against software executions on benchmark test functions.
Active perception refers to a theoretical approach to the study of perception grounded on the idea that perceiving is a way of acting, rather than a cognitive process whereby the brain constructs an internal representation of the world. The operational principles of active perception can be effectively tested by building robot-based models in which the relationship between perceptual categories and the body-environment interactions can be experimentally manipulated. In this paper, we study the mechanisms of tactile perception in a task in which a neuro-controlled anthropomorphic robotic arm, equipped with coarse-grained tactile sensors, is demanded to perceptually discriminate between spherical and ellipsoid objects. The results of this work demonstrate that evolved continuous time non-linear neural controllers can bring forth strategies to allow the arm to effectively solve the discrimination task.
Evolvable Hardware(EHW) has been proposed as a promising technology for adaptive systems in last few years.However, in practical applications, evolutionary algorithms(EAs) often need numerous generations to search a new solution. In general, a mistaken system is damaged if it cannot restore in time, so the inefficiency problem has become an obstacle of developing adaptive and evolvable hardware. This paper analyzes how those three factors as genotype, algorithm, and methodology affect the efficiency of the EAs, as well as to what extent of their influence respectively, then proposes parallel and recursive decomposition (PRD) as a new decomposition strategy to accelerate the adaptation process from methodology perspective. Finally, some adaptive combination logical circuits are implemented on Xilinx Virtex-II Pro (XC2VP20) FPGA. The results demonstrate that PRD has more improvement on adaptation speed than some previous strategies.
Given a territory composed of basic geographical units, the delineation of local labour market areas (LLMAs) can be seen as a problem in which those units are grouped subject to multiple constraints. In previous research, standard genetic algorithms were not able to find valid solutions, and a specific evolutionary algorithm was developed. The inclusion of multiple ad hoc operators allowed the algorithm to find better solutions than those of a widely-used greedy method. The experimentation process showed that the rate of success of each operator in generating good individuals is different and evolves with time. We therefore propose different adaptive alternatives that modify the probabilities of application of each operator throughout the evolutionary process, and compare the results of such adaptive approaches with previous results and a greedy method.
This paper investigates the feasibility of using Genetic Programming in dynamically changing environments to evolve decision trees for classification problems and proposes an new version of Genetic Programming called Adaptive Genetic Programming. It does so by comparing the performance or classification error of Genetic Programming and Adaptive Genetic Programming to that of Gradient Descent in abruptly and progressively changing environments. To cope with dynamic environments, Adaptive Genetic Programming incorporates adaptive control parameters, variable elitism and culling. Results show that both Genetic Programming and Adaptive Genetic Programming are viable algorithms for dynamic environments yielding a performance gain over Gradient Descent for lower dimensional problems even with severe environment changes. In addition, Adaptive Genetic Programming performs slightly better than Genetic Programming, due to faster recovery from changes in the environment.
To improve the calculation cost and the convergence to optimal solutions for multi-peak optimization problems with multiple dimensions, we propose a new evolutionary algorithm, which is an Adaptive Plan system with Genetic Algorithm (APGA). This is an approach that combines the global search ability of a GA and an Adaptive Plan (AP) with excellent local search ability. The APGA differs from GAs in how it handles design variable vectors (DVs). GAs generally encode DVs into genes, and handle them through GA operations. However, the APGA encodes the control variable vectors (CVs) of the AP, which searches for local minima, into its genes. CVs determine the global behavior of the AP, and DVs are handled by the AP in the optimization process of the APGA. In this paper, the Variable Neighborhood range Control (VNC), which changes a neighborhood range based on an individual's situation—fitness, is introduced into the APGA to dramatically improve the convergence up to the optimal solution. The APGA/VNC is applied to some benchmark functions to evaluate its performance. We confirmed satisfactory performance through these various benchmark tests.
Abstract—The goal of this project is to develop an agent to play the first-person shooter game Unreal Tournament 2004, a fast-paced and dynamic environment that demands that the agent must be capable of making decisions quickly. An additional goal of this project is to explore evolutionary computation as a means for learning the rule sets used to control the game-playing agent. The agent's behavior is controlled by a rule-based system, which looks at multiple high-level conditions, such as whether the agent is weak, and determines a single high-level action, such as to head for the nearest known healing source. Using an evolutionary computation approach, in which the behavior is evolved over a number of generations, the agent learns increasingly better strategies for its environment. Through the work in this project, we are exploring several research questions, including the development of successful vocabulary of high-level conditions and actions for the rule set, the challenges of using the evolutionary process to hone a rule set.
In this paper, we propose a new algorithm, named JACC-G, for large scale optimization problems. The motivation is to improve our previous work on grouping and adaptive weighting based cooperative coevolution algorithm, DECC-G, which uses random grouping strategy to divide the objective vector into subcomponents, and solve each of them in a cyclical fashion. The adaptive weighting mechanism is used to adjust all the subcomponents together at the end of each cycle. In the new JACC-G algorithm: (1) A most recent and efficient Differential Evolution (DE) variant, JADE, is employed as the subcomponent optimizer to seek for a better performance; (2) The adaptive weighting is time-consuming and expected to work only in the first few cycles, so a detection module is added to prevent applying it arbitrarily; (3) JADE is also used to optimize the weight vector in adaptive weighting process instead of using a basic DE in previous DECC-G. The efficacy of the proposed JACC-G algorithm is evaluated on two sets of widely used benchmark functions up to 1000 dimensions.
Traditional particle swarm optimization (PSO) suffers from the premature convergence problem, which usually results in PSO being trapped in local optima. This paper presents an adaptive learning PSO (ALPSO) based on a variant PSO learning strategy. In ALPSO, the learning mechanism of each particle is separated into three parts: its own historical best position, the closest neighbor and the global best one. By using this individual level adaptive technique, a particle can well guide its behavior of exploration and exploitation. A set of 21 test functions were used including un-rotated, rotated and composition functions to test the performance of ALPSO. From the comparison results over several variant PSO algorithms, ALPSO shows an outstanding performance on most test functions, especially the fast convergence characteristic.
Over the last two decades several methods have been proposed for handling functional constraints while solving nonlinear optimization problems using Evolutionary Algorithms (EA). However EAs have inherent difficulty in dealing with equality constraints. This paper presents an Agent-based Memetic Algorithm (AMA) for solving nonlinear optimization problems with equality constraints. A new learning process for agents is introduced specifically for handling the equality constraints in the evolutionary process. The basic concept is to reach a point on the equality constraint from its current position by the selected individual agents. The proposed algorithm is tested on a set of standard benchmark problems. The preliminary results show that the proposed technique works very well on those benchmark problems.
Most optimization algorithms suffer from a significant deterioration in performance as the dimensionality and complexity of the problem search space increases. Also these algorithms, given certain configurations, typically show markedly improved performance on a particular problem only to exhibit poor performance on another. The first issue could be resolved by using a cooperative algorithm to divide the problem complexity among its participating algorithms, making the problem easier to solve. The second issue could then be resolved with the use of differently configured participating algorithms within the overall cooperative algorithm. This paper investigates the possibility of combining different population-based algorithms within a cooperative algorithm. The aim is to take advantage of different algorithm characteristics regarding parameter settings, explorative/exploitative capacity, convergence speed and other behaviors in finding solutions to various optimization problems.
Grid workflow scheduling problem has been a research focus in grid computing in recent years. Various deterministic or meta-heuristic scheduling approaches have been proposed to solve this NP-complete problem. These existing algorithms, however, are not suitable to tackle a class of workflows, namely the time-varying workflow, in which the topologies change over time. In this paper, we propose an ant colony optimization (ACO) approach to tackle such kind of scheduling problems. The algorithm evaluates the overall performance of a schedule by tracing the sequence of its topologies in a period. Moreover, integrated pheromone information is designed to balance the workflow's cost and makespan. In the case study, a 9-task grid workflow with four topologies is used to test our approach. Experimental results demonstrate the effectiveness and robustness of the proposed algorithm.
In this paper, an extraction and classification feature approach of biological sequences based on profiles built using an association analysis is proposed. The most important features of the approach are: i) The use of data mining techniques to perform knowledge extraction from biological sequences. Specifically an association analysis process is proposed as a methodology for discovering interesting relationships hidden in biological data sets; and ii) Some learning classifiers are proposed to be trained using binary profiles obtained from the association analysis process. These learning methods were applied over a sequence structure layer of secondary structure predictors to analyze the performance of association rules as a pattern extraction method. Some experiments were carried out to validate the proposed approach obtaining very promising results.
The optimization of network coding is a relatively new area for evolutionary algorithms, as very few efforts have so far been reported. This paper is concerned with the design of an effective Genetic Algorithm (GA) for tackling the network coding problem (NCP). Differing from previous relevant works, the proposed GA is designed based on a permutation representation, which not only allows each chromosome to record a specific network protocol and coding scheme, but also makes it easy to integrate useful problem-specific heuristic rules into the algorithm. In the new GA, a more general fitness function is proposed, which, besides considering the minimization of network coding resources, also takes into account the maximization of the rate actually achieved. This new fitness function makes the proposed GA more suitable for the case of dynamic network coding, where any link could be cut off at any time, and consequently, the target rate might become unachievable even if all nodes allow coding. Based on the new representation and fitness function, other GA related techniques are modified and employed accordingly and carefully. Comparative experiments show that the proposed GA clearly outperforms previous methods.
Since the just-in-time (JIT) problems have special importance in the real world, various methods have been developed by researchers to solve this kind of problem more precisely and in a minimal possible time. Most of JIT problems are NP-hard, thus many of these methods have been created based on metaheuristics. In this paper the single-machine scheduling problem with a common due date is considered in which performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Here we use a solving method based on Scatter Search metaheuristic in which the features of optimal solution of single machine minimization are utilized appropriately. The proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs. In addition to having a good solution time, we got new upper bounds in our numerical examples using proposed method.
One of the main tasks software testing involves is the generation of the test inputs to be used during the test. Due to its expensive cost, the automation of this task has become one of the key issues in the area. Recently, this generation has been explicitly formulated as the resolution of a set of constrained optimisation problems. Differential Evolution (DE) is a population based evolutionary algorithm which has been successfully applied in a number of domains, including constrained optimisation. We present a test data generator employing DE to solve each of the constrained optimisation problems, and empirically evaluate its performance for several DE models. With the aim of comparing this technique with other approaches, we extend the experiments to the Breeder Genetic Algorithm and face it to DE, and compare different test data generators in the literature with the DE approach. The results present DE as a promising solution technique for this real-world problem.
Artificial immune systems (AIS) have been widely applied to many fields such as data analysis, multimodal function optimization, error detection, etc. In this paper, we show how AIS can be used for system-level fault diagnosis. Experimental results from a thorough simulation study and theoretical analysis demonstrate the effectiveness of the AIS-based diagnosis approach for different small and large systems in both the worst and average cases, making it a viable addition to the existing diagnosis algorithms.
Modeling of solid oxide fuel cell (SOFC) stack-based systems is a powerful approach that can provide useful insights into the nonlinear dynamics of the system without the need for formulating complicated systems of equations describing the electrochemical and thermal properties. This paper presents an efficient genetic programming approach for modeling and simulation of SOFC output voltage versus fuel utilization behavior. This method is shown to outperform the state-of-the-art radial basis function neural network approach for SOFC modeling.
An evolutionary random search algorithm is proposed for learning of the optimum bid in double auction markets where the agents are either members of the population of sellers or the population of buyers. Sellers and buyers are attempting to learn their optimum bid or offer prices, respectively, that maximize their individual gain in the next round of the game. The performance of the algorithm presented in this paper is compared with the performance of the genetic learning algorithm previously used for the same purpose. Multiple simulations demonstrate that the new algorithm converges faster to a market equilibrium. Learning in the presence of uncertainties is also studied.
The attention to self-organization as a feasible metaphor for dealing with the growing complexity of today's software systems is constantly growing. In particular, by adopting self-organization, systems can adapt to highly dynamic environments by local interaction among system's components. As a consequence, the global behavior of the system can be regarded as an emergent property since it appears by a process emerging from local interactions among components. The corresponding system dynamics is usually non-linear and complex so that the adoption of simulation and verification techniques in the early design stage becomes essential to carry out an effective design. Accordingly, in this paper we discuss a hybrid approach relying on stochastic simulation and probabilistic model checking and show a possible application on a problem called collective sort taken as a case study. To this end, the PRISM probabilistic model checker is adopted as a concrete tool for analyzing emergent properties of collective sort. Finally, a discussion of the corresponding results is provided.
Particle Swarm Optimization (PSO) has typically been used with small swarms of about 50 particles. However, PSO is more efficiently parallelized with large swarms. We formally describe existing topologies and identify variations which are better suited to large swarms in both sequential and parallel computing environments. We examine the performance of PSO for benchmark functions with respect to swarm size and topology. We develop and demonstrate a new PSO variant which leverages the unique strengths of large swarms. 'Hearsay PSO' allows for information to flow quickly through the swarm, even with very loosely connected topologies. These loosely connected topologies are well suited to large scale parallel computing environments because they require very little communication between particles. We consider the case where function evaluations are expensive with respect to communication as well as the case where function evaluations are relatively inexpensive. We also consider a situation where local communication is inexpensive compared to external communication, such as multicore systems in a cluster.
There are various kinds of evolutionary computations (ECs) and they have their own merits and demerits. For example, PSO (Particle Swarm Optimization) shows high ability during initial period in general, whereas DE (Differential Evolution) shows high ability especially in the latter period in search to find more accurate solutions. This paper proposes a novel and integrated framework to effectively combine the merits of several evolutionary computations. There are five distinctive features in the proposed framework. 1) There are several individual pools, and each pool corresponds to one EC. 2) Parents do not necessarily belong to the same EC: for example, a GA type individual can be a spouse of a PSO type individual. 3) Each incorporated EC has its own evaluated value (EV), and it changes according to the best fitness value at each generation. 4) The number of individuals in each EC changes according to the EV. 5) All of the individuals have their own lifetime to avoid premature convergence; when an individual meets lifetime, the individual reselect EC, and the probability of each EC to be selected depends on the EV. In the proposed framework, therefore, more individuals are allotted to the ECs which show higher performance than the other at each generation: effective usage of individuals is enabled. In this way, this framework can make use of merits of incorporated ECs. Original GA, original PSO and original DE are used to construct a simple proposed framework-based system. We carried out experiments using well-known benchmark functions. The results show that the new system outperformed there incorporated ECs in 9 functions out of 13 functions.
Computer-assisted testing systems are promising in generating tests efficiently and effectively for evaluating a person's skill. This paper develops a novel intelligent testing system for both teachers and students. Equipped with user-friendly interfaces and administrative modules, the proposed system offers the following features and advantages: 1) Self-adaptive. Item attributes in an item bank are adaptively updated to reflect students' newest learning states. 2) Reliable. Tests with high assessment qualities are reliably generated, satisfying teachers' multiple requirements. 3) Flexible for generating parallel tests with identical test ability, especially useful for makeup exams. For students, the system is used for exercises and self-evaluation. For teachers, the system is a good helper for generating tests with different requirements. In this paper, the self-adaptation strategy and the ant colony optimization based test composition (ACO-TC) method are firstly described. ACO, an advanced computational intelligence algorithm, is used for searching high-quality results. Then the proposed testing system is introduced. The performance of the system is analyzed for composing tests in different situations.
Type-1 fuzzy system is able to provide an inference mechanism to reason with imprecise information, but it is unable to do so under linguistic and numerical uncertainties. While the incorporation of interval type-2 fuzzy set can offer a model for handling further uncertainty, it is relatively difficult to extract the footprint of uncertainty information. In addition, fuzzy systems are unable to automatically acquire the linguistic rules to model the problem. In this paper, an interval type-2 fuzzy neural model named Interval type-2 Neural Fuzzy Inference System (IT2NFIS) is proposed, to automatically generate the linguistic model with interval type-2 fuzzy sets and thus their faced uncertainties. The structure identification algorithm is based on Piaget's cognitive view of an action-driven cognitive development in human. IT2NFIS is evaluated on Nakanishi data sets and the results show that IT2NFIS is comparable if not superior to other models.
Genetic algorithms (GAs) are classical evolutionary computation methods, which have a wild application prospect. This paper proposes an improved genetic algorithm, named the isoline genetic algorithm (IGA), for numerical optimization. The proposed algorithm utilizes the population to construct isolines of fitness values in the search space. These isolines can be used to depict the fitness landscape in the current search area and direct the search process. IGA predicts the location of the peak by calculating the centroid of isolines. The promising centroid will enter the population. Numerical experiments on thirteen benchmark functions reveal the effectiveness and efficiency of IGA. The experimental results indicate improvements in both convergence speed and solution accuracy.
This paper proposes an multi-objective evolutionary algorithm. The algorithm is based on OMOEA-II. A new linear breeding operator with lower-dimensional crossover and copy operation is used. By using the lower-dimensional crossover, the complexity of searching is decreased so the algorithm converges faster. The orthogonal crossover increase probability of producing potential superior solutions, which helps the algorithm get better results. Ten unconstrained problems in CEC 2009 Multi-objective Optimization Competition are used to test the algorithm. For three problems, the obtained solutions are very close to the true Pareo Front, and for one problem, the obtained solutions distribute on part of the true Pareo Front.
This paper studies the difference between Persistent Random Constants (PRC) and Digit Concatenation as methods for generating constants. It has been shown that certain problems have different fitness landscapes depending on how they are represented, independent of changes to the combinatorial search space, thus changing problem difficulty. In this case we show that the method for generating the constants can also influence how hard the problem is for Genetic Programming.
In this article, a novel multiobjective variable string length real coded genetic fuzzy clustering scheme for clustering microarray gene expression data has been proposed. The proposed technique automatically evolves the number of clusters along with the clustering result. The multiobjective variable string length clustering technique encodes the cluster centers in its chromosomes and simultaneously optimizes two fuzzy validity indices namely PBM index and Xie-Beni validity measure. In the final generation, it produces a set of nondominated solutions, from which the best solution is selected using Silhouette index which is independent of the number of clusters. The corresponding chromosome length provides the number of clusters. The proposed method is applied on three publicly available real life gene expression data. Superiority of the proposed method over some other well known clustering algorithms has been demonstrated quantitatively.
In this paper we quantitatively analyze the probability distributions generated by an EDA during the search. In particular, we record the probabilities to the optimal point, the point with the highest probability and that of the best individual of the population, when the EDA is solving a trap function. By using different structures in the probabilistic models we can analyze the influence of the structural model accuracy on the aforementioned probability values. In addition, the objective function values of these points are contrasted with their probability values in order to study the connection between the function and the probabilistic model. The results provide new information about the behavior of the EDAs and they open a discussion regarding which are the minimum (in)dependences necessary to reach the optimum.
Previous research in supervised and unsupervised anomaly detection normally employ a static model of normal behaviour (normal-model) throughout the lifetime of the system. However, there are real world applications such as swarm robotics and wireless sensor networks where what is perceived as normal behaviour changes accordingly to the changes in the environment. To cater for such systems, dynamically updating the normal-model is required. In this paper, we examine the requirements from a range of distributed autonomous systems and then propose a novel unsupervised anomaly detection architecture capable of online adaptation inspired by the vertebrate immune system.
Option pricing is one of the challenging problems in finance. Finding the best time to exercise an option is a even more challenging problem, especially since the price of the underlying assets change rapidly. In this work, we study complex path dependent options by exploiting and extending a novel idea that we proposed earlier using a nature inspired meta-heuristic algorithm. Ant Colony Optimization (ACO). ACO has been used extensively in combinatorial optimization problems and recently in dynamic applications such as mobile ad-hoc networks where the objective is find a shortest path. However, in finance, especially in option pricing, we look for best time to exercise an option. Specifically, we use ants to decide on the best time to exercise so that the holder of the option contract will get the maximum benefit from his/her investment. Our algorithm and implementation suggests a better way to price options than traditional techniques such as Monte Carlo simulation or binomial lattice algorithm. Our pricing results compare very well with other techniques and at the same time the computational cost is reduced to a large extent. ~
Due to complex nonlinear data pattern in time series regression, forecasting techniques had been categorized in different ways, and the literature is also full of differing opinions, thus, it is difficult to make a general conclusion. In the recent years, the support vector regression (SVR) model has been widely used to solve nonlinear time series regression problems. This investigation presents a short-term traffic forecasting model by employing SVR with genetic algorithm and simulated annealing algorithm (GA-SA) to determine the suitable parameter combination in the SVR model. Consequently, a numerical example of traffic flow values from northern Taiwan is used to demonstrate the forecasting performance of the proposed SVRGA-SA model is superior to the seasonal autoregressive integrated moving average (SARIMA) time series model.
The importance of finding or making thermostable enzymes in different industries have been highlighted. Therefore, it is inevitable to understand the features involving in enzymes' thermostability. Different approaches have been employed to extract or manufacture thermostable enzymes. Here we have looked at features contributing to Endo-1,4,-xylanase (EC 126.96.36.199) thermostability, the key enzyme with possible applications in waste treatment, fuel and chemical production and paper industries. We trained different neural networks with/without feature selection and classification modelling on all available xylanase enzymes amino acids sequences to find features contributing to enzyme thermal stability. Frequency of Met (-0.006) and Lys (-0.010) showed the weakest correlation with xylanase enzymes' optimum temperature; the count of Lie (0.326) and Glu (0.324) showed the strongest direct correlation while the count of oxygen (-0.38) and frequency of Gln (-0.299) reversely correlated to xylanase enzyme thermostability Six modelling methods (Quick, Dynamic, Multiple, Prune, Exhaustive Prune and RBFN) applied on all available xylanase sequences with/without validation set and/or feature selection (24 neural networks); with estimated accuracy between 80% to 90%; the best one (90.638%) in Multiple method of neural network without validation set and without feature selection, exactly in the most complicated neural network. The weakest accuracy (80.560%) found in Dynamic method of neural network without feature selection and with validation set. In 6 out of 24 neural networks generated here, the frequency of Gln was the most important feature contributing to optimum xylanase temperature and in 4 networks count of other charged residues were the most important features. Considering the analytical and performance evaluation of different models examined here, we found Multiple model generated in modelling without feature selection and validation set a good candidate to use for testing thermostability in 7030 virtually generated Bacillus halodurans mutants. We applied this model on those mutants and in some of them up to 10ºC thermal stability improvement were observed.
Different Multi-Objective Optimization Methods (MOOM) for solving Multi-Objective Optimization Problems (MOOP) have been suggested in the literature. These methods often comprise two stages (not necessarily sequential): i) the search for the Pareto-optimal set and ii) the selection of a single solution from this non-dominated set. Various studies comparing performance of particular aspects of these methods have been carried out. However, a theoretical support that changes on the preferences of a Decision Maker (DM) will be reflected in the same way on the solution of the MOOP given by the MOOM has not been presented. In this work the quality of the relation between a scalarizing function parameters and the solutions produced by a MOOM was been assessed. It will used to compare the performance of different methods available in the literature. This study was performed using some benchmark test problems, with two criteria.
In this paper assessment of different Genetic Algorithm (GA) selection, crossover and mutation techniques in term of convergence to the optimal solution for single objective reactive power optimization problem is presented and investigated. The problem is formulated as a nonlinear optimization problem with equality and inequality constraints. Also, in this paper a simple cost appraisal for the potential annual cost saving of these GA techniques due to reactive power optimization will be conducted. Wale & Hale 6 bus system was used in this paper study.
A Geometric Collaborative Evolutionary (GCE) model is presented and studied. An asynchronous search process is facilitated through a gradual propagation of the fittest individuals' genetic material into the population. Recombination is guided by the geometrical structure of the population. The GCE model specifies three strategies for recombination corresponding to three subpopulations (societies of agents). Each individual in the population acts as an autonomous agent with the goal of optimizing its fitness being able to communicate and select a mate for recombination. Complex dynamics in the proposed system are investigated against the probability of dominance between agent societies. A significant emergent pattern and corresponding transition interval are emphasized in several experiments. Percolation-like behavior is also detected, suggesting the complete dominance of one agent society over the entire population under certain conditions. Furthermore, numerical results indicate a good performance of the proposed evolutionary asynchronous search model.
In biology, the importance of environmental feedback to the process of embryogenesis is well understood. In this paper we explore the introduction of a local fitness to an artificial developmental system, providing an artificial analogue to the natural phenomenon. First, we define a highly simplified model of vasculogenesis, an environment-based toy problem in which we can evaluate our strategies. Since the use of a global fitness function for local feedback is likely too computationally expensive, we introduce the notion of a neighbourhood-based 'local fitness' function. This local fitness serves as an environmental-feedback guide for the developmental system. The result is a developmental analogue of guided hill-climbing, one which significantly improves the performance of an artificial embryogeny in the evolution of a simplified vascular system. We further evaluate our model in a collection of randomly generated two-dimensional geometries, and show that inclusion of local fitness helps allay some of the problem difficulty in irregular environments. In the process, we also introduce a novel and systematic means of generating bounded, connected two-dimensional geometries.
This paper applies the Differential Evolution (DE) algorithm to the task of automatic fuzzy clustering in a Multi-objective Optimization (MO) framework. It compares the performances of four recently developed multi-objective variants of DE over the fuzzy clustering problem, where two conflicting fuzzy validity indices are simultaneously optimized. The resultant Pareto optimal set of solutions from each algorithm consists of a number of non-dominated solutions, from which the user can choose the most promising ones according to the problem specifications. A real-coded representation of the search variables, accommodating variable number of cluster centers, is used for DE. The performances of four DE variants have also been contrasted to that of two most well-known schemes of MO clustering namely the Non Dominated Sorting Genetic Algorithm ( NSGA II) and Multi-Objective Clustering with an unknown number of Clusters K (MOCK). Experimental results over four artificial and four real life datasets of varying range of complexities indicates that DE holds immense promise as a candidate algorithm for devising MO clustering schemes.
In evolutionary robotics, controllers are often designed in simulation, then transferred onto the real system. Nevertheless, when no accurate model is available, controller transfer from simulation to reality means potential performance loss. It is the reality gap problem. Unmanned aerial vehicles are typical systems where it may arise. Their locomotion dynamics may be hard to model because of a limited knowledge about the underlying physics. Moreover, a batch identification approach is difficult to use due to costly and time consuming experiments. An automatic identification method is then needed that builds a relevant local model of the system concerning a target issue. This paper deals with such an approach that is based on coevolution of models and tests. It aims at improving both modeling and control of a given system with a limited number of manipulations carried out on it. Experiments conducted with a simulated quadrotor helicopter show promising initial results about test learning and control improvement.
Experiment-based optimization using Evolutionary Algorithms (EAs) is a promising approach for real world problems in which construction of simulation models is difficult. When using EAs, three difficulties have to be considered. Currently, two difficulties, uncertainty of the evaluation value and limitation of the number of evaluations, are active research topics into EAs. However, the other difficulty, avoidance of extreme trial, has not entered into the spotlight. Extreme trials run the 'risk' of breakdown of the optimized object and its measurement instruments in experiment-based optimization. In this paper, we consider that the extreme trial means a large constraint violation of the problems, and install the concept of 'risky-constraint'. Then, to avoid risky-constraint violation, we propose a violation avoidance method and combine it with Multi-objective Evolutionary Algorithms (MOEAs). The effectiveness of the proposed method is confirmed through numerical experiments and real common-rail diesel engine experiments.
This work studies the problem of premature convergence due to the lack of diversity in Estimation of Distributions Algorithms. This problem is quite important for these kind of algorithms since, even when using very complex probabilistic models, they can not solve certain optimization problems such as some deceptive, hierarchical or multimodal ones. There are several works in literature which propose different techniques to deal with premature convergence. In most cases, they arise as an adaptation of the techniques used with genetic algorithms, and use randomness to generate individuals. In our work, we study a new scheme which tries to preserve the population diversity. Instead of generating individuals randomly, it uses the information contained in the probability distribution learned from the population. In particular, a new probability distribution is obtained as a variation of the learned one so as to generate individuals with less probability to appear on the evolutionary process. This proposal has been validated experimentally with success with a set of different test functions.
This paper describes an evolutionary clustering algorithm, which can partition a given dataset automatically into the optimal number of groups through one shot of optimization. The proposed method is based on a recently developed evolutionary computing technique known as the Bacterial Evolutionary Algorithm (BEA). The BEA draws inspiration from a biological phenomenon of microbial evolution. Unlike the conventional mutation, crossover and selection operaions in a GA (Genetic Algorithm), BEA incorporates two special operations for evolving its population, namely the bacterial mutation and the gene transfer operation. In the present context, these operations have been modified so as to handle the variable lengths of the chromosomes that encode different cluster groupings. Experiments were done with several synthetic as well as real life data sets including a remote sensing satellite image data. The results estabish the superiority of the proposed approach in terms of final accuracy.
Bare Bones Particle Swarm Optimization (BBPSO) is a powerful algorithm, which has shown potential to solving multimodal optimization problems. Unfortunately, BBPSO may also get stuck into local optima when optimizing functions with many local optima in high dimensional search space. In previous attempts an approach was developed which consists of a jump strategy combined with PSO in order to escape from local optima and promising results have been obtained. In this paper, we combine BBPSO with a jump strategy when no fitness improvement is observed. The jump strategy is implemented based on the Gaussian or the Cauchy probability distribution. The algorithm was tested on a suite of well-known benchmark multimodal functions and the results were compared with those obtained by the standard BBPSO algorithm and with BBPSO with re-initialization. Simulation results show that the BBPSO with the jump strategy performs well in all functions investigated. We also notice that the improved performance is due to a successful number of Gaussian or Cauchy jumps.
Many real-world dynamic optimisation problems have constraints, and in certain cases not only the objective function changes over time, but the constraints also change as well. However, in academic research there is not many research on continuous dynamic constrained optimization, and particularly there is little research on whether current numerical dynamic optimization algorithms would work well in dynamic constrained environments nor there is any numerical dynamic constrained benchmark problems. In this paper, we firstly investigate the characteristics that might make a dynamic constrained problems difficult to solve by existing dynamic optimization algorithms. We then introduce a set of numerical dynamic benchmark problems with these characteristics. To verify our hypothesis about the difficulty of these problems, we tested several canonical dynamic optimization algorithms on the proposed benchmarks. The test results confirm that dynamic constrained problems do have special characteristics that might not be solved effectively by some of the current dynamic optimization algorithms. Based on the analyses of the results, we propose a new algorithm to improve the performance of current dynamic optimization methods in solving numerical dynamic constrained problems. The test results show that the proposed algorithm achieves superior results compared to the tested existing dynamic optimization algorithms.
Regulatory networks are complex networks. This paper addresses the challenge of modelling these networks. The Boolean representation is chosen and supported as a suitable representation for an abstract approach. In in-silico experiments, two different bio-inspired techniques are applied to the reverse engineering of a Boolean regulatory network: as a search method a Genetic Algorithm is applied and an indirect method based on Artificial Development and tuned to this application, is proposed. Both methods are challenged at reverse engineering a known network - the yeast cell-cycle network model. Presented results show that they are both successful in reverse engineering the considered network.
Developing systems that support people in everyday life in a discrete and effective way is an ultimate goal of a new generation of technical systems. Physiological computing represents one means of creating a system to sense the user, analyse users' responses to system adaptation and respond dynamically. This process of adaptation is achieved by creating a biocybernetic loop that may operate on several, simultaneous timescales (minutes/hours/weeks/ months/years). In terms of architecture, it is argued that a "sense-analyse-react" system requires middleware with closed-loop control consisting of: (1) a tangible tier concerned with sensors and actuators, (2) a reflective tier containing a flexible representation of the user to guide system adaptation, and (3) an application tier representing application scenarios and the context for adaptation and evolution.
The CoSMoS project aims to develop reusable tools and techniques for complex systems modelling and simulation. Using process-oriented software design techniques, we have built a concurrent model of continuous space, usable in a variety of complex systems simulations. In this paper, we describe how we refactored our space model to allow our simulations to run in an efficient and highly-scalable manner across clusters of commodity machines---and, in particular, to support distributed simulation and visualisation on the Tromsø Display Wall.
For living organisms, the robustness property is capital. For almost all of them, robustness rhymes with self-repairing. Indeed, organisms are subject to various injuries brought by the environment. To maintain their integrity, organisms are able to regenerate dead parts of themselves. This mechanism, commonly named self-repairing, is interesting to reproduce. Many works exist about self-repairing in robotics and electronics but fewer are in our domain of interest, artificial embryogenesis. In this paper, we show the self-repairing abilities of our model, Cell2Organ, designed to generate artificial creature for artificial worlds. This model has previously been presented in [1]
Population-based algorithms, such as Differential Evolution (DE), Particle Swarm Optimization (PSO), Genetic Algorithms (GAs), and Evolutionary Strategies (ES), are commonly used approaches to solve complex problems from science and engineering. They work with a population of candidate solutions. In this paper, a novel center-based sampling is proposed for these algorithms. Reducing the number of function evaluations to tackle with high-dimensional problems is a worthwhile attempt; the center-based sampling can open a new research area in this direction. Our simulation results confirm that this sampling, which can be utilized during population initialization and/or generating successive generations, could be valuable in solving large-scale problems efficiently. Quasi- Oppositional Differential Evolution is briefly discussed as an evidence to support the proposed sampling theory. Furthermore, opposition-based sampling and center-based sampling are compared in this paper. Black-box optimization is considered in this paper and all details about the conducted simulations are provided.
An approach of population dynamics and clustering for permutative problems is presented in this paper. Diversity indicators are created from solution ordering and its mapping is shown as an advantage for population control in metaheuristics. Differential Evolution Algorithm is modified using this approach and vetted with the Quadratic Assignment Problem. Extensive experimentation is conducted on benchmark problems in this area.
The paper presents an evolutionary robotics model of the Rover Mars robot. This work has the objective to investigate the possibility of using an alternative sensor system, based on infrared sensors, for future rovers capable of performing autonomous tasks in challenging planetary terrain environments. The simulation model of the robot and of Mars terrain is based on a physics engine. The robot control system consists of an artificial neural network trained using evolutionary computation techniques. An adaptive threshold on the infrared sensors has been evolved together with the neural control system to allow the robot to adapt itself to many different environmental conditions. The properties of the behavior obtained after the evolutionary process has been tested by measuring the generalization performance of the rover under various terrain conditions and especially under rough terrain condition. In addition, the dynamics of the co-evolution between the controller and the threshold has been analyzed. Those analysis show that different pathways have been explored by the evolutionary process in order to adapt the sensing abilities and the control system.
We conduct an evolutionary simulation to explore the coevolution of language and a language-related ability, intentionality sharing. Our simulation shows that during the evolution of a simple informative language, communicative success helps optimize the level of intentionality sharing in the population. This study illustrates a selective role of language communications on language-related abilities, and assists the discussion of the uniqueness of language-related abilities based on comparative studies.
Reservoir modeling is an on-going activity during the production life of a reservoir. One challenge to constructing accurate reservoir models is the time required to carry out a large number of computer simulations. This research investigates a competitive co-evolutionary algorithm to select a small number of informative reservoir samples to carry out computer simulation. The simulation results are also used to co-evolve the computer simulator proxies. We have developed a co-evolutionary system incorporating various techniques to conduct a case study. Although the system was able to select a very small number of reservoir samples to run the computer simulations and use the simulation data to construct simulator proxies with high accuracy, these proxy models do not generalize very well on a larger set of simulation data generated from our previous study. Nevertheless, we have identified that including a test-bank in the system helped mitigating the situation. We will conduct more systematic analysis of the competitive co-evolutionary dynamics to improve the system performance.
Efficient heuristics are required for on-line optimization problems where search-based methods are unfeasible due to frequent dynamics in the environment. This is especially apparent when operating on combinatorial NP-compete problems involving a large number of items. However, designing new heuristics for these problems may be a difficult and time-consuming task even for domain experts. Therefore, automating this design process may benefit the industry when facing new and difficult optimization problems. The Distributor's Pallet Packing Problem (DPPP) is the problem of loading a pallet of non-homogenous items coming off a production line and is an instance of a range of resource-constrained, NP-complete, scheduling problems that are highly relevant for practical tasks in the industry. Common heuristics for the DPPP typically decompose the problem into two sub-problems; one of pre-scheduling all items on the production line and one of packing the items on the pallet. In this paper we concentrate on a two dimensional version of the DPPP and the more realistic scenario of having knowledge about only a limited set of the items on the production line. This paper aims at demonstrating that such an unknown heuristic may be evolved by Gene Expression Programming and Cooperative Coevolution. By taking advantage of the natural problem decomposition, two species evolve heuristics for pre-scheduling and packing respectively. We also argue that the evolved heuristics form part of a developmental stage in the construction of the finished phenotype, that is, the loaded pallet.
Game playing has always provided an exciting avenue of research in Artificial Intelligence. Various methodologies and techniques have been developed to build intelligent game players. Coevolution has proven to be successful in learning how to play games with no prior game knowledge. In this paper we develop a coevolutionary system for the General Game Playing framework, where absolutely nothing is known about the game beforehand, and enhance it using Cultural Algorithms. In order to test the effectiveness of complementing coevolution with cultural algorithms, we play matches in several games between our player, a random player and one trained using standard coevolution.
We propose a new evolutionary algorithm for the multiple knapsack problem (MKP) which uses multiple representations. Previous, successful approaches for the MKP have included a weight-coded, order-based representation, as well as a grouping representation enhanced by a dominance condition to restrict search. We propose a representation-switching genetic algorithm which periodically transforms the representation of individuals between these two representations. We show that this new hybrid algorithm outperforms the previous approaches.
Search Based Software Engineering (SBSE) is an evolving field where meta-heuristic techniques are applied to solve many software engineering problems. One area of SBSE, where considerable research is underway, is software testing. We see much application of meta-heuristics search techniques for generating input test data. But most of the work in this area is concentrated on test data generation from source code. We see very little application of such techniques to testing from other sources such as requirement and design models. Zhan and Clark applied such techniques to generate test data for Simulink models. This paper extends the work of Zhan and Clark by investigating the application of Genetic Algorithms (GAs) to Simulink models and then statistically compares the results to the existing work, which is mainly based on Simulated Annealing (SA).
The lifespan, and hence utility, of sensornets is limited by the energy resources of individual motes. Network designers seek to maximise energy efficiency while maintaining an acceptable network Quality of Service. However, the interactions between multiple tunable protocol parameters and multiple sensornet performance metrics are generally complex and unknown. In this paper we address this multi-dimensional optimisation problem by two distinct approaches. Firstly, we apply a Design Of Experiments approach to obtain a generalised linear interaction model, and from this derive an estimated near-optimal solution. Secondly, we apply the Two-Archive evolutionary algorithm to improve solution quality for a specific problem instance. We demonstrate that, whereas the first approach yields a more generally applicable solution, the second approach yields a broader range of viable solutions at potentially lower experimental cost.
Different approaches are in use to solve the problem of tomographic reconstruction, which is an inverse problem. Four different approaches; three variations of multiplicative algebraic reconstruction technique (MART) and a new approach based on genetic algorithms (GA), are evaluated and compared in the paper. The approaches are applied to the reconstruction of specimens from time-of-flight data collected by ultrasound transmission tomography. The time-of-flight data is simulated without taking into consideration the diffraction effects of ultrasound which is reasonably valid, only when the impedance mismatch in the specimen under consideration is small. Also it is assumed that the specimen under consideration consists of a maximum of three different materials with the goal being to identify the number, shape, and location of the inclusions in the specimen. The sensitivity of the various algorithms to the parameters involved, performance of various algorithms in terms of errors in reconstruction and time taken for the reconstruction are studied and presented here. Further the performance of the algorithms when the input data are contaminated with noise is presented. It is observed that although GA takes more time than MART, GA is reliable and accurate and scores much better than MART in dealing with problems where only limited data is available for the reconstruction.
Tuning the parameters of an evolutionary algorithm (EA) to a given problem at hand is essential for good algorithm performance. Optimizing parameter values is, however, a non-trivial problem, beyond the limits of human problem solving.In this light it is odd that no parameter tuning algorithms are used widely in evolutionary computing. This paper is meant to be stepping stone towards a better practice by discussing the most important issues related to tuning EA parameters, describing a number of existing tuning methods, and presenting a modest experimental comparison among them. The paper is concluded by suggestions for future research -- hopefully inspiring fellow researchers for further work.
This work deals with the comparison of performance of two selected evolutionary algorithms (EA) in the task of optimization of the control of chaos. The main aim of this work is to show that evolutionary algorithms are capable of optimization of chaos control, leading to satisfactory results and to show extreme sensitivity of quality of results on the selection of EA, setting-up of EA, construction of cost function (CF) and any small change in the CF design. As a model of deterministic chaotic system, the two dimensional Henon map was used. Two complex targeting cost functions were tested in this work. The optimization was realized in several ways, each one for another evolutionary algorithm or another desired periodic orbit and behavior of system. The evolutionary algorithms, SOMA (Self-Organizing Migrating Algorithm) and DE (Differential Evolution) were used in several versions. For each version, repeated simulations demonstrated the robustness of the used method and constructed CF. Finally, the obtained results are compared.
We study the evolution of cooperation using the Prisoner's Dilemma as a metaphor of the tensions between cooperators and non-cooperators, and evolutionary game theory as the mathematical framework for modeling the cultural evolutionary dynamics of imitation in a population of unrelated individuals. We investigate the interplay between network reciprocity (a mechanism that promotes cooperation in the Prisoner's Dilemma by restricting interactions to adjacent sites in spatial structures or neighbors in social networks) and conformity (the tendency of imitating common behaviors). We confirm previous results on the improved levels of cooperation when both network reciprocity and conformity are present in the model and evolution is carried on top of degree-homogeneous graphs, such as rings and grids. However, we also find that scale-free networks are no longer powerful amplifiers of cooperation when fair amounts of conformity are introduced in the imitation rules of the players. Such weakening of the cooperation-promoting abilities of scale-free networks is the result of a less biased flow of information in such topologies, making hubs more susceptible of being influenced by less-connected neighbors.
The field of evolutionary art is generally concerned with evolving patterns that have little constraint. This paper describes an evolutionary art system that is constrained to form flag designs, following a set of common design patterns. The resulting genotype representation, genetic operators and forms of user interaction are chosen to allow an exploration of 'flag space', as well as allowing the user to rapidly focus on aspects of specific designs. The utility of the approach is demonstrated by evolving flag designs using image similarity and by user-directed evolution.
Many objective optimization is a natural extension to multi-objective optimization where the number of objectives are significantly more than five. The performance of current state of the art algorithms (e.g. NSGA-II, SPEA2) is known to deterioate significantly with increasing number of objectives due to the lack of adequate convergence pressure. It is of no surprise that the performance of NSGA-II on some constrained many-objective optimization problems [1] (e.g., DTLZ5-(5,M), M = 10, 20) in an earlier study [2] was far from satisfactory. Till date, research in many-objective optimization has focussed on two major areas (a) dimensionality reduction in the objective space and (b) preference ordering based approaches. This paper introduces a novel evolutionary algorithm powered by epsilon dominance (implemented within the framework of NSGA-II) and controlled infeasibility for improved convergence while the critical set of objectives is identified through a nonlinear dimensionality reduction scheme. Since approaching the Pareto-optimal front from within the feasible search space will need to overcome the problems associated with low selection pressure, the mechanism to approach the front from within the infeasible search space is promising as illustrated in this paper. The performance of the proposed algorithm is compared with NSGA-II (original, with crowding distance measure) and NSGA-II (epsilon dominance) on the above set of constrained multiobjective problems to highlight the benefits.
Evolutionary algorithms were originally designed for the optimization of unconstrained problems. When applied to constrained real-world problems, for example to the optimization of the operation of pipeless chemical batch plants, the constraints have to be taken into account to generate feasible solutions. This paper examines different approaches of constraint handling within the framework of an evolutionary scheduling algorithm and a heuristic schedule builder. Repair algorithms eliminate most infeasibilities before passing a candidate solution to the schedule builder. This is shown to be more efficient than dealing with the constraints inside the schedule builder or simply rejecting infeasible solutions.
The classical portfolio problem is a problem of distributing capital to a set of stocks. By adapting to the change of stock prices, this study proposes an portfolio investment strategy based on an evolutionary method named 'Genetic Network Programming' (GNP). This method makes use of the information from Technical Indices and Candlestick Chart. The proposed portfolio model, consisting of technical analysis rules, are trained to generate investment advice. Experimental results on the Japanese stock market show that the proposed investment strategy using Time Adapting GNP (TA-GNP) method outperforms other traditional models in terms of both accuracy and efficiency. We also compared the experimental results of the proposed model with the conventional GNP based methods, GA and Buy&Hold method to confirm its effectiveness, and it is clarified that the proposed investment strategy is effective on the portfolio optimization problem.
Many real-world problems demand a feasible solution to satisfy physical equilibrium, stability, or certain properties which require an additional lower level optimization problem to be solved. Although such bilevel problems are studied somewhat in the context of a single objective in each level, there are not many studies in which multiple conflicting objectives are considered in each level. Bilevel multi-objective optimization problems offer additional complexities, as not every lower level Pareto-optimal front has a representative solution to the upper level Pareto-optimal front and that only a tiny fraction of participating lower level fronts make it to the upper level front. A couple of recent studies by the authors have suggested a viable EMO method. In this paper, we analyze the difficulties which a bilevel EMO procedure may face in handling such problems and present a systematic construction procedure for bilevel optimization test problems. Based on the suggested principles, we propose five test problems which are scalable in terms of number of variables and objectives, and which enable researchers to evaluate different phases of a bilevel problem solving task. The test problem construction procedure is interesting and may motivate other researchers to extend the idea to develop further test problems.
Optimising compilers present their authors with an intractable design space. A substantial body of work has used heuristic search techniques to search this space for the purposes of adapting optimisers to their environment. To date, most of this work has focused on sequencing, tuning and guiding the actions of atomic hand-written optimisation phases. In this paper we explore the adaption of optimisers at a deeper level by demonstrating that it is feasible to automatically build a non-trivial optimisation phase, for a simple functional language, using Grammatical Evolution. We show that the individuals evolved compare well in performance to a hand-written optimisation phase on a range of benchmarks. We conclude with proposals of how this work and its applications can be extended.
The non-revisiting genetic algorithm (NrGA) is extended to handle continuous search space. The extended NrGA model, Continuous NrGA (cNrGA), employs the same tree-structure archive of NrGA to memorize the evaluated solutions, in which the search space is divided into non-overlapped partitions according to the distribution of the solutions. cNrGA is a bi-modulus evolutionary algorithm consisting of the genetic algorithm module (GAM) and the adaptive mutation module (AMM). When GAM generates an offspring, the offspring is sent to AMM and is mutated according to the density of the solutions stored in the memory archive. For a point in the search space with high solution-density, it infers a high probability that the point is close to the optimum and hence a near search is suggested. Alternatively, a far search is recommended for a point with low solution-density. Benefitting from the space partitioning scheme, a fast solution-density approximation is obtained. Also, the adaptive mutation scheme naturally avoid the generation of out-of-bound solutions. The performance of cNrGA is tested on 14 benchmark functions on dimensions ranging from 2 to 40. It is compared with real coded GA, differential evolution, covariance matrix adaptation evolution strategy and two improved particle swarm optimization. The simulation results show that cNrGA outperforms the other algorithms for multi-modal function optimization.
This article presents an evolutionary approach for solving a difficult problem of combinatorial optimization, the DCMST (Degree-Constrained Minimum Spanning Tree Problem). Three variations of the Continuous-Space Embedding Genetic Algorithm (described in [1]) are proposed here for performing the optimization task. The results achieved by these three algorithm variations have been compared with four other existing algorithms according to three merit criteria: i) quality of the best solution found; ii) computational effort spent by the algorithm, and; iii) convergence tendency of the population. The three variations of the algorithm have provided better results for both solution quality and population convergence, with reasonable computational cost, in tests performed for 25-node and 50-node test instances. The results suggest that the proposed algorithms are well suited for dealing with the problem under study.
An investigation on control mechanism using particle swarm optimization (PSO) to suppress the vibration of flexible plate has been carried out. Active vibration control (AVC) is implemented for the case of single-input single output (SISO), and the controller is realized in linear parametric form where all parameters are arbitrarily chosen by applying the working mechanism of PSO. The objective function is the mean-squared error of the observed vibration signal. The performance of the controller is assessed in terms of level of attenuation achieved in the power spectral density (PSD) of the observed signal.
Many current Evolutionary Algorithms suffer from a tendency to prematurely loose their capability to incorporate new genetic material, resulting in a stagnation in suboptimal points. To successfully apply these methods on increasingly complex problems, the ability to generate useful variations leading to continuous improvements is vital. Nevertheless, there is a major difficulty in finding computational extensions to the evolutionary paradigm that ensures a continuous emergence of new qualitative solutions, as the essence of the Darwinian paradigm -- the natural selection -- acts as a stabilizing force, keeping the population into an evolutionary equilibria. It is suggested that replacing the survival of the fittest paradigm with a cooperative framework, where individuals are highly specialized on different exploring and exploitive strategies, results in a highly efficient, non-convergent, sustainable search process, where new optima emerge continually. Proposed technique is validated on the test suits of CEC'08 Large Scale Optimization Contest.
We examine a potential role of signalling crosstalk in Artificial Cell Signalling Networks (ACSNs). In this research, we regard these biochemical networks as subsets of collectively autocatalytic (i.e., organizationally closed) reaction networks being able to both self-maintain and to carry out a distinct signal processing function. These signalling crosstalk phenomena occur naturally when different biochemical networks become mixed together where a given molecular species may contribute simultaneously to multiple ACSNs. It has been reported in the biological literature, that crosstalk may have effects that are both constructive (e.g., coordinating cellular activities, multi-tasking) and destructive (e.g., premature programmed cell death). In this paper we demonstrate how crosstalk may enable distinct closed ACSNs to cooperate with other. From a theoretical point of view, this work may give new insights for the understanding of crosstalk in natural biochemical networks. From a practical point view, this investigation may provide novel applications of crosstalk in engineered ACSNs.
Cytocomputation is a computational paradigm based upon the macromolecular activity inside the cytoplasm of the biological cells. This paradigm can be used either as a source of inspiration for proposing novel computational architectures, or as a framework for modeling biological processes at the intracellular and intercellular levels. This paper presents the main characteristics of the paradigm and describes its implementation on the ubichip, a hardware platform specifically designed to support bioinspired architectures.
Fuzzy logic controller (FLC) is well-known of its robustness to parameter variations and ability to reject noise. But its design requires defining many parameters. In this work, a systematic and simple procedure is proposed to develop an integrated fuzzy based guidance law which consists of three FLC. Each one of them is activated in a region of the interception. To allow smooth transition between these controllers, another fuzzy-based switching system is introduced. The parameters of all the fuzzy controllers which include the distribution of the membership functions and the rules are simply obtained by observing the function of each controller. Furthermore, these parameters are optimally tuned by the method of genetic algorithms through solving an optimization problem to minimize the interception time, the missile acceleration commands and the miss distance. The simulation results show that the proposed procedure was able to generate a guidance law with a satisfactory performance.
This paper discusses two important features of electronic design through evolutionary processes; creativity and innovation. Hence, conventional design methodologies are discussed and compared with their counterparts via evolutionary processes. An evolutionary search is used as an engine for discovering new designs for a real world application. Attempts to extract some useful principles from the evolved designs are presented and results are compared to conventional design topologies for the same problems.
Genetic algorithms (GA) do have some advantages over gradient-based methods for solving topology design optimization problems. However, their success depends largely on the geometric representation used. In this work, an morphological representation of geometry using wide Bezier curve is applied and evaluated to be efficient and effective in producing good results via a structure design problem subjected to uncertainty. A wide Bezier curve is a Bezier curve with width or cross section. Based on the morphology of living creatures, a geometric representation scheme has been developed that works by specifying a skeleton which defines the underlying topology/connectivity of a structural continuum together with segments of material surrounding the skeleton. This scheme facilitates the transmission of topological and shape characteristics across generations in the evolutionary process and amplify the representation variability. The proposed scheme coupled with a GA is presented to perform topology optimization.
Music classification is a complex problem which has gained high relevance for organizing large music collections. Different parameters concerning feature extraction, selection, processing and classification have a strong impact on the categorization quality. Since it is very difficult to design a deterministic approach which provides the efficient parameter tuning, we haven chosen a heuristic approach. In our work we apply and compare different evolution strategies for the optimization of feature selection and consolidation using three pre-defined personal user categories. Concepts of local search operators with domain-specific knowledge and self-adaptation are examined. Several suggestions based on an empirical study are discussed and ideas for future work are given.
In this paper, we propose a multiobjective evolutionary approach to design a microwave heating device. The goal is to heat the maximum amount of water, above certain temperature, and spending the minimum energy. The device is modeled as a loss multilayer dielectric irradiated by microwave power. The resulting bi-objective problem is then solved using SPEA2 and a set of solutions is obtained. The results show that SPEA2 finds a higher number of non-dominated solution when compared with the traditional approaches used in this problem, within lower computational cost.
In the paper we present a novel approach based on applying a modern metaheuristic Gene Expression Programming (GEP) to detecting web application attacks. This class of attacks relates to malicious activity of an intruder against applications, which use a database for storing data. The application uses SQL to retrieve data from the database and web server mechanisms to put them in a web browser. A poor implementation allows an attacker to modify SQL statements originally developed by a programmer, which leads to stealing or modifying data to which the attacker has not privileges. While the attack consists in modification of SQL queries sent to the database, they are the only one source of information used for detecting attacks. Intrusion detection problem is transformed into classification problem, which the objective is to classify SQL queries between either normal or malicious queries. GEP is used to find a function used for classification of SQL queries. Experimental results are presented on the basis of SQL queries of different length. The findings show that the efficiency of detecting SQL statements representing attacks depends on the length of SQL statements. Additionally we studied the impact of classification threshold on the obtained results.
Change detection enables an evolutionary algorithm operating in a dynamic environment to respond with undertaking necessary steps for maintaining its performance. We consider two major types of change detection, population--based and sensor--based. For population--based we show its relation to statistical hypothesis testing and analyze it using receiver--operating characteristics. For sensor--based the relationship between detection success and number of employed sensors is studied and the dimensionality problem is addressed. Finally, we discuss how both types of change detection compare to each other.
Genetic Algorithm (GA) generally maintains diverse solutions of good quality to be obtained in multi-objective problems, while Particle Swarm Optimization (PSO) shows fast convergence to the optimum solution. Past studies indicated that search abilities can be improved by simply coupling these algorithms; GA compensates for the low diversity of PSO, while PSO compensates for the high computational costs of GA. In this research, a further improvement was achieved by investigating the configurations of the two methods when used in a fully-coupled hybrid algorithm. The new hybrid algorithm was validated using standard test function problems, and it was consequently showed that the new hybrid algorithm has better performance than the simply coupled hybrid algorithm, not to mention pure GA and pure PSO. The new method was also applied to a real-world engineering design problem; it optimizes the geometry of a diesel engine combustion chamber to reduce exhaust emissions, such as NOx and soot. The results demonstrated the superior applicability of the present method to real-world design problems.
Epistasis, or gene-gene interaction, is a ubiquitous phenomenon that is inadequately addressed in human genetic studies. There are few tools that can accurately identify high-order epistatic interactions, and there is a lack of general understanding as to how epistatic interactions fit into genetic architecture. Here we approach both problems through the lens of genetic programming (GP). It has recently been proposed that increasing open-endedness of GP will result in more complex solutions that better acknowledge the complexity of human genetic datasets. Moreover, the solutions evolved in open-ended GP can serve as model organisms in which to study general effects of epistasis on phenotype. Here we introduce a prototype computational evolution system that implements an open-ended GP and generates organisms that display epistatic interactions. These interactions are significantly more prevalent and have a greater effect on fitness than epistatic interactions in organisms generated in the absence of selection.
Combining the good features of particle swarm optimization (PSO) and artificial immune system (AIS) we propose new Immunized PSO (IPSO) algorithm. This algorithm is used to identify generalized Hammerstein model by employing functional link artificial neural network (FLANN) architecture for the nonlinear static part and an adaptive linear combiners for the linear dynamic part of the model. Simulation study of few benchmark Hammerstein models is carried out through simulation study and the results obtained are compared with those obtained by standard PSO and AIS based method. Comparison of results demonstrate superior performance of the proposed methods over its PSO and AIS counterpart in terms of response matching, accuracy of identification and convergence speed achieved.
The materialist dialectical method is a philosophical investigative method to analyze aspects of reality as complex processes composed by integrating units named poles. Dialectics has experienced considerable progress in the 19th century, with Hegel's dialectics and, in the 20th century, with the works of Marx, Engels, and Gramsci, in Philosophy and Economics. The movement of poles through their contradictions is viewed as a dynamic process with intertwined phases of evolution and revolutionary crisis. Santos et al. introduced the Objective Dialectical Classifier (ODC), a non-supervised self-organized map for classification. As a case study, we used ODC to classify 181 magnetic resonance synthetic multispectral images composed by proton density, T1- and T2-weighted synthetic brain images. Comparing ODC to k-means, fuzzy c-means, and Kohonen's self-organized maps, concerning with image fidelity indexes as estimatives of quantization distortion, we proved that ODC can reach the same quantization performance as optimal non-supervised classifiers like Kohonen's self-organized maps.
In this paper, differential evolution (DE) algorithms are presented to solve the generalized assignment problem (GAP), which is basically concerned with finding the minimum cost assignment of jobs to agents such that each job is assigned to exactly one agent, subject to capacity constraint of agents. The first algorithm is unique in terms of solving a discrete optimization problem by a traditional differential evolution working on a continuous domain. The second one is a discrete/combinatorial variant of the traditional differential evolution algorithm working on a discrete domain. The objective is to present a continuous optimization algorithm dealing with discrete spaces. Both algorithms are hybridized with a "blind" variable neighborhood search (VNS) algorithm to further enhance the solution quality, especially to end up with feasible solutions. They are tested on a benchmark suite from OR Library. Computational results are promising for a continuous algorithm such that without employing any problem-specific heuristics and speed-up methods, the cDE variant hybridized with a "blind" VNS local search was able to generate competitive results to its discrete counterpart.
Differential Evolution (DE) is a novel evolutionary approach capable of handling non-differentiable, non-linear and multi-modal objective functions. DE has been consistently ranked as one of the best search algorithm for solving global optimization problems in several case studies. Mutation operation plays the most significant role in the performance of a DE algorithm. This paper proposes a new mutation operator with the help of Laplace distributed random numbers. The proposed algorithm is examined for a set of ten benchmark, global optimization problems having different dimensions. The numerical results show that the incorporation of the proposed mutant vector helps in improving the performance of DE in terms of final objective function value and convergence rate.
This paper presents Differential Evolution with Self-adaptation and Local Search for Constrained Multiobjective Optimization algorithm (DECMOSA-SQP), which uses the self-adaptation mechanism from DEMOwSA algorithm presented at CEC 2007 and a SQP local search. The constrained handling mechanism is also incorporated in the new algorithm. Assessment of the algorithm using CEC 2009 special session and competition on constrained multiobjective optimization test functions is presented. The functions are composed of unconstrained and constrained problems. Their results are assessed using the IGD metric. Based on this metric, algorithm strengths and weaknesses are discussed.
In the commonly used DE/rand/1 variant of differential evolution the primary mechanism of generating new solutions is the perturbation of a randomly selected point by a difference vector. The newly selected point may, if good enough, then replace a solution from the current generation. As the magnitude of difference vectors diminishes as the population converges, the size of moves made also diminishes, an oft-touted and obvious benefit of the approach. Additionally, when the population splits into separate clusters difference vectors exist for both small and large moves. Given that a replaced solution is not the one perturbed to create the new, candidate solution, are the large difference vectors responsible for movement of population members between clusters? This paper examines the mechanisms of small and large moves, finding that small moves within one cluster result in solutions from another being replaced and so appearing to move a large distance. As clusters tighten this is the only mechanism for movement between them.
The contribution treats properties of a new evolutionary algorithm – Differential Migration, and provides a comparison with other algorithms of this type. Differential Migration is tested with standard artificial neural network benchmark and standard test functions for performance comparison. Sensitivity analysis is conducted in order to specify the optimal parameters and their influence to the algorithm performance. SOMA (Self-Organizing Migration Algorithm) and Differential Evolution are used as a reference, and the results are compared with Differential Migration.
This paper investigates improvements to the fitness function in Genetic Programming to better solve binary classification problems with unbalanced data. Data sets are unbalanced when there is a majority of examples for one particular class over the other class(es). We show that using overall classification accuracy as the fitness function evolves classifiers with a performance bias toward the majority class at the expense of minority class performance. We develop four new multi-objective fitness functions which consider the accuracy of majority and minority class separately to address this learning bias. Results using these fitness functions show that good accuracy for both the minority and majority classes can be achieved from evolved classifiers while keeping overall performance high and balanced across the two classes.
This paper proposes a new algorithm to identify and compose building blocks based on minimum mutual information criterion. Building blocks are interpreted as common subsequences between good individuals. The proposed algorithm can extract building blocks in population explicitly. The additively decomposable problems and hierarchical decomposable problems are used to validate the algorithm. The results are compared with Bayesian Optimization Algorithm, Hierarchical Bayesian Optimization Algorithm, and Chi-square Matrix. This proposed algorithm is simple, easy to tune and fast.
In order to alleviate user fatigue of interactive genetic algorithms with individual's fuzzy and stochastic fitness, we propose a surrogate model assisted algorithm by using directed fuzzy graph to extract user cognitive. According to cut-set level and interval dominance probability, we present the approaches to construct a directed fuzzy graph of an evolutionary population, and based on the fuzzy graph, calculate an individual's crisp fitness. By applying the fuzzy entropy, the chance of data sampling is achieved to obtain the reliable samples for training the surrogate model. We adopt support vector regression machine as the surrogate model, train it using the sampled individuals and their crisp fitness, and use traditional genetic algorithm to optimize the surrogate model for some generations before the interactive one, providing guided individuals to the user to accelerate the evolution. We quantitatively analyze the performance of the presented algorithm in alleviating user fatigue and increasing more opportunities to find the satisfactory individuals. Finally, we apply our algorithm to the fashion evolutionary design system to demonstrate its efficiency.
The cost estimates for receiving unsolicited commercial email messages, also known as spam, are threatening. Spam has serious negative impact on the usability of electronic mail and network resources. In addition, it provides a medium for distributing harmful code and/or offensive content. The work in this paper is motivated by the dramatic increase in the volume of spam traffic in recent years and the promising ability of ant colony optimization in data mining. Our goal is to develop an ant-colony based spam filter and to empirically evaluate its effectiveness in predicting spam messages. We also compare its performance to three other popular machine learning techniques: Multi-Layer Perceptron, Naïve Bayes and Ripper classifiers. The preliminary results show that the developed model can be a remarkable alternative tool in filtering spam; yielding better accuracy with considerably smaller rule sets which highlight the important features in identifying the email category.
During the legal investigation of Enron Corporation, the U.S. Federal Regulatory Commission (FERC) made public a substantial data set of the company's internal corporate emails. This work presents a genetic algorithm (GA) approach to social network analysis (SNA) using the Enron corpus. Three SNA metrics, degree, density, and proximity prestige, were applied to the detection of networks with high email activity and presence of important actors with respect to email transactions. Quantitative analysis revealed that density and proximity prestige captured networks of high activity more so than degree. Subsequent qualitative analysis indicated that there were trade-offs in the selection of SNA metrics. Examination of the discovered social networks showed that density and proximity prestige isolated networks involving key actors to a greater extent than degree. In particular, density picked out interesting patterns in terms of email volume, while proximity prestige better isolated key actors at Enron. The roles of the particular actors picked out by the networks as reasons for their prominence are also discussed.
This paper proposes the use of a particle swarm optimization algorithm to the Field Programmable Gate Arrays (FPGA) placement problem. Two different versions of the particle swarm optimization algorithm are proposed. The first is a discrete version that solves the FPGA placement problem entirely in the discrete domain, while the second version is continuous in nature. Both versions are applied to several wellknown FPGA benchmarks and the results are compared to those obtained by an academic placement tool that is based on adaptive simulated annealing. Results show that the proposed methods are competitive for small and medium-sized problems. For large-sized problems, the proposed methods provide very close results.
Hyper-heuristics or 'heuristics to chose heuristics' are an emergent search methodology that seeks to automate the process of selecting or combining simpler heuristics in order to solve hard computational search problems. The distinguishing feature of hyper-heuristics, as compared to other heuristic search algorithms, is that they operate on a search space of heuristics rather than directly on the search space of solutions to the underlying problem. Therefore, a detailed understanding of the properties of these heuristic search spaces is of utmost importance for understanding the behaviour and improving the design of hyper-heuristic methods. Heuristics search spaces can be studied using the metaphor of fitness landscapes. This paper formalises the notion of hyper-heuristic landscapes and performs a landscape analysis of the heuristic search space induced by a dispatching-rule-based hyper-heuristic for production scheduling. The studied hyper-heuristic spaces are found to be 'easy' to search. They also exhibit some special features such as positional bias and neutrality. It is argued that search methods that exploit these features may enhance the performance of hyper-heuristics.
We present a new distributed genetic algorithm that can be used to extract useful information from distributed, large data over the network. The main idea of the proposed algorithm is to determine how many and which individuals move between subpopulations at each site adaptively. In addition, we present a method to help individuals from other subpopulation not be weeded out but adapt to new subpopulation. We apply our distributed genetic algorithm to the feature subset selection task which has been one of the active research topics in machine learning. We used 7 data sets from UCI Machine Learning Repository to compare the performance of our approach with that of the single, centralized genetic algorithm. As a result, the proposed algorithm produced better performance than the single genetic algorithm in terms of the classification accuracy with the feature subsets.
This paper introduces two new distributed learning algorithms : Incremental Particle Swarm Optimization (IPSO) and Diffusion Particle Swarm Optimization (DPSO). These algorithms are applied for distributed identification of nonlinear processes using cooperation among adaptive nodes. Identification of four standard nonlinear plants have been carried out through simulation to assess the performance of these algorithms. The results indicate better or identical identification performance offered by the proposed distributed algorithms compared to that offered by the conventional PSO based algorithm. The improvement is observed in terms of CPU time, accuracy in response matching and speed of convergence.
Evolutionary computing in general and distributed online evolutionary computation in particular are hard problems in terms of monitoring, evaluation, generating functionality, and performance. We strive to complement current approaches and develop mechanisms which do not require the ex post effort of controlling the outcome of the computation. Instead, the goal of our research agenda foresees techniques which allow evolutionary and distributed computing to solve the problems above a priori. To support such an intrinsic system we make use of the powerful tool of algebra. Thus, this paper sheds some light on algebraic theories which allow the establishment of strong connections between biological concepts, automata theory, and the algebraic theories associated with them. We compile various contributions from different areas of research of the last few years discussing the algebraisation of biological systems and functions and their relation to automata theory and algebra. We highlight the role of category theory and abstract algebra and outline why these concepts are highly relevant for computational approaches inspired by biological mechanisms.
In evolutionary algorithms, the occurrence of premature convergence is due to the lack of effective diversity maintenance procedures in the population during the search process. The effect may be more predominant if the optimization problem also includes general constraints. In this paper, we propose a diversity enhanced Adaptive Evolutionary Programming (DivEnh-AEP) method by using an external memory to solve some of the static constrained optimization problems of CEC 2006. The external memory stores past diverse solutions which are systematically injected back into the evolving population to enhance diversity. This diversity enhancement procedure does not consume any function evaluations. Experimental results with two different constraint handling methods show improved performance due to the proposed diversity enhancement procedure.
This paper presents a diversity enhanced particle swarm optimizer (DivEnh-PSO) which uses an external memory to enhance the diversity of the swarm and to discourage premature convergence. The external memory holds selected past solutions with good diversity. Selected past solutions are periodically injected into the swarm. This approach does not require additional function evaluations as past solutions are used to enhance diversity. Experiments were conducted on multimodal and composition test problems with and without coordinate rotations. The test results indicate improved performance of the DivEnh-PSO in solving multimodal problems when compared with the same PSO implementation without diversity enhancement.
Linear and nonlinear quantitative structure-activity relationship (QSAR) models and docking score functions were developed for dihydrofolate reductase (DHFR) inhibition by cycloguanil derivatives using small molecule descriptors derived from MOE and in silico docking energies. The best QSAR models and docking score functions were identified when using artificial neural networks optimized by evolutionary computation. The resulting models can be used to identify key descriptors for DHFR inhibition and are useful for high-throughput screening of novel drug compounds.
In this paper we investigate a Self-Adaptive Differential Evolution algorithm (jDE) where F and CR control parameters are self-adapted and a multi-population method with aging mechanism is used. The performance of the jDE algorithm is evaluated on the set of benchmark functions provided for the CEC 2009 special session on evolutionary computation in dynamic and uncertain environments.
The Ubichip is a reconfigurable digital circuit with special bio-inspired mechanisms that supports dynamic partial reconfigurability in a flexible and efficient way. This paper presents an adaptive size neural network model with incremental learning that exploits these capabilities by creating new neurons and connections whenever it is needed and by destroying them when they are not used during some time. This neural network, composed of a perception layer and an action layer, is validated on a robot simulator, where neurons are created under the presence of new perceptions. Furthermore, links between perceptions and actions are created, reinforced, and destroyed following a Hebbian approach. In this way, the neural controller creates a model of its specific environment, and learns how to behave in it. The neural controller is also able to adapt to a new environment by forgetting previously unused knowledge, freeing thus hardware resources.We present some results about the neural controller and how it manages to characterize some specific environments by exploiting the dynamic hardware topology support offered by the ubichip.
Peer-to-peer based distributed computing environments can be expected to be dynamic to greater of lesser degree. While node losses will not usually lead to catastrophic failure of a population-based optimisation algorithm, such as particle swarm optimisation, performance will be degraded unless the lost computational power is replaced. When resources are replaced, one must consider how to utilise newly available nodes as well as the loss of existing nodes. In order to take advantage of newly available nodes, new particles must be generated to populate them. This paper proposes two methods of generating new particles during algorithm execution and compares the performance of each approach, then investigates a hybridised approach incorporating both mechanisms.
Gene Expression Programming(GEP) is a kind of heuristic method based on evolutionary computation theory. Gene Expression Programming has been used to evolve decision tree with high accuracy comparable to C4.5. In this paper, we proposed a simple but effective dynamic boundary method for gene expression programming evolved decision tree to improve the performance of tree splitting and classification accuracy. Results show that our method can find better generalized ability rules and it is especially suitable for difficult problems with many attributes in different boundaries.
This paper examines the decentralized recognition of groups within a multiagent normative society in dynamic environments. In our case, a social group is defined based on the set of social norms used by its members. These social norms regulate interactions under certain situations, and situations are determined by the environmental conditions. Environmental conditions might change unexpectedly, and so should the notion of social group for each agent. Consequently, agents need mechanisms to adjust their notion of group dynamically and accordingly the agents with whom it is socially related. In this work we analyze how different algorithms (whitelisting, blacklisting, labelling), that allow agents to recognize the others as members of a certain social group, behave in these dynamic environments. Simulation results are shown, confirming that the limited memory approach reacts better against environmental changes. Moreover we compare two approaches that regulate the adaptation of the relevance of norms and the notion of group: the unlimited normative memory and the limited memory.
Cellular evolutionary algorithms usually use a single neighborhood structure for local selection. When a new solution is to be generated by crossover and/or mutation for a cell, a pair of parent solutions is selected from its neighbors. The current solution at the cell is replaced with the newly generated offspring if the offspring has the higher fitness value than the current one. That is, the "replace-if-better" policy is used for the replacement of the current solution. Local selection, crossover, mutation and replacement are iterated at every cell in cellular algorithms. A recently proposed multiobjective evolutionary algorithm called MOEA/D by Zhang and Li (2007) can be viewed as a cellular algorithm where each cell has its own scalarizing fitness function with a different weight vector. We can introduce a spatial structure to MOEA/D by the Euclidean distance between weight vectors. Its main difference from standard cellular algorithms is that a newly generated offspring for a cell is compared with not only the current solution of the cell but also its neighbors for local replacement in MOEA/D. In this paper, we examine the effect of local replacement on the search ability of a cellular version of MOEA/D. Whereas the same neighborhood structure was used for local selection and local replacement in the original MOEA/D, we examine the use of different neighborhood structures for local selection and local replacement. It is shown through computational experiments on multiobjective 0/1 knapsack problem with two, four and six objectives that local replacement plays an important role in MOEA/D especially for many-objective optimization problems.
In this paper, a new method for path planning is proposed using a genetic algorithm (GA). Our method has two key advantages over existing GA methods. The first is a novel environment representation which allows a more efficient method for obstacles dilation in comparison to current cell based approaches that have a tradeoff between speed and accuracy. The second is the strategy we use to generate the initial population in order to speed up the convergence rate which is completely novel. Simulation results show that our method can find a near optimal path faster than computational geometry approaches and with more accuracy in smaller number of generations than GA methods.
In this paper, we review several proposals for guide selection in Multi-Objective Particle Swarm Optimization (MOPSO) and compare them with each other in terms of convergence, diversity and computational times. The new proposals made for guide selection, both personal best (pbest) and global best (gbest), are found to be extremely effective and perform well compared to the already existing methods. The combination of selection methods for choosing gbest and pbest is also studied and it turns out that there exist certain combinations which yield an overall superior performance outperforming the others on the tested benchmark problems. Furthermore, two new proposals namely velocity trigger (as a substitute for 'turbulence operator') and a new scheme of boundary handling is made.
Recently a great emphasis has been given on autonomous decentralized networks (ADNs) wherein constituent nodes carry out specific tasks collectively. Their dynamic and constrained nature along with the emerging need for offering quality of service (QoS) assurances drive the necessity for effective network control mechanisms. This study focuses on designing a robust and self-adaptable congestion control mechanism which aims to be simple to implement at the individual node, and involve minimal information exchange, while maximizing network lifetime and providing QoS assurances. Our approach combats congestion by mimicking the collective behavior of bird flocks having global self-* properties achieved collectively without explicitly programming them into individual nodes. The main idea is to 'guide' packets (birds) to form flocks and flow towards the sink (global attractor), whilst trying to avoid congestion regions (obstacles). Unlike the bio-swarm approach of Couzin, which is formulated on a metrical space, our approach is reformulated on to a topological space (graph of nodes), while repulsion/attraction forces manipulate the direction of motion of packets. Our approach provides sink direction discovery, congestion detection and traffic management in ADNs with emphasis on Wireless Sensor Networks (WSNs). Performance evaluations show the effectiveness of our self-adaptable mechanism in balancing the offered load and in providing graceful performance degradation under high load scenarios compared to typical conventional approaches.
This paper proposes a modification of Differential Evolution (DE) schemes. During the offspring generation, a local search is applied, with a certain probability to the scale factor in order to generate an offspring with high performance. In a memetic fashion, the main idea in this paper is that the application of a different perspective in the search of a DE can assist the evolutionary framework and prevent the undesired effect of stagnation which DE is subject to. Two local search algorithms have been tested for this purpose and an application to the individual with the best performance has been proposed. The resulting algorithms seem to significantly enhance the performance of a standard DE scheme over a broad set of test problems. Numerical results show that the modified algorithm is very efficient with respect to a standard DE in terms of final solution detected, convergence speed and robustness.
This paper is the part II of a paper composed of two parts. In the part I a memetic approach consisting of applying a local search to the scale factor of a Differential Evolution framework in order to generate an off-spring with a high quality was proposed. The part II proposes the application of the scale factor local search within a Differential Evolution framework which integrates a self-adaptive update of the control parameters. In other words, unlike for the part I, the scale factor local search is applied to a an algorithmic framework characterized by multiple scale factors over the individuals of the population and scale factor updates during the evolution. Two simple local search logics have been tested, the first one employs the golden section search and the second one a hill-climber. The local search algorithms thus assist the global search and generates offspring with high performance which are subsequently supposed to promote the generation of better solutions within the evolutionary framework. Numerical results show that the hybridization is beneficial and able to outperform in many cases both the classical Differential Evolution and a Self-Adaptive Differential Evolution recently proposed in literature.
Multi-objective optimization is an essential and challenging topic in the domains of engineering and computation because real-world problems usually include several conflicting objectives. Current trends in the research of solving multi-objective problems (MOPs) require that the adopted optimization method provides an approximation of the Pareto set such that the user can understand the tradeoff between objectives and therefore make the final decision. Recently, an efficient framework, called MOEA/D, combining decomposition techniques in mathematics and optimization methods in evolutionary computation was proposed. MOEA/D decomposes a MOP to a set of single-objective problems (SOPs) with neighborhood relationship and approximates the Pareto set by solving these SOPs. In this paper, we attempt to enhance MOEA/D by proposing two mechanisms. To fully employ the information obtained from neighbors, we introduce a guided mutation operator to replace the differential evolution operator. Moreover, a update mechanism utilizing a priority queue is proposed for performance improvement when the SOPs obtained by decomposition are not uniformly distributed on the Pareto font. Different combinations of these approaches are compared based on the test problem instances proposed for the CEC 2009 competition. The set of problem instances include unconstrained and constrained MOPs with variable linkages. Experimental results are presented in the paper, and observations and discussion are also provided.
Accurate fitness estimates are notoriously difficult to attain in cooperative coevolution, as it is often unclear how to reward the individual parts given an evaluation of the evolved system as a whole. This is particularly true for cooperative approaches to neuroevolution, where neurons or neuronal groups are highly interdependent. In this paper we investigate this problem in the context of evolving neural networks for unstable control problems. We use measures from information theory and neuroscience to reward neurons in a neural network based on their degree of participation in the behavior of the network as a whole. In particular, we actively seek networks with high complexity and little redundancy, and argue that this can lead to efficient evolution of robust controllers. Preliminary results support this claim, and indicate that measures from information theory may provide meaningful information about the role of each neuron in a network.
The best choice problem is an important class of the theory of optimal stopping rules. In this article, we present the Cross-Entropy method for solving the multiple best choice problem with the minimal expected ranks of selected objects. Computational results showed that the Cross-Entropy method is producing high-quality solution.
Estimation of Distribution Algorithm (EDA) is a novel evolutionary computation, which mainly depends on learning and sampling mechanisms to manipulate the evolutionary search, and has been proved a potential technique for complex problems. However, EDA generally spend too much time on the learning about the probability distribution of the promising individuals. The paper propose an improved EDA based on copula theory (copula-EDA) to enhance the learning efficiency, which models and samples the joint probability function by selecting a proper copula and learning the marginal probability distributions of the promising population. The simulating results prove the approach is easy to implement and is validated on several problems.
This paper examines an intelligent recommendation strategy implementation for managing a long short hedge fund and reports on performance during market conditions at the onset of the liquidity crisis. A hedge fund utilizes long and short trading to manage an investment portfolio consisting of allocations to cash and share equity positions. This results in a combined long short portfolio that is leveraged to obtain a potentially greater market exposure with borrowed cash from short selling and is also hedged to protect against market downturns. The paper also examines effects of parameters for fuzzy rule base specification on trading performance.
There are various discussions on the evolution of cooperation on different pairs of interaction network for playing games and the replacement network for imitation of strategies. This paper aims at clarifying the topological relationship between these networks that facilitates the evolution of cooperation by focusing on the intensity of selection for imitation process of strategies. We constructed an agent-based model of the evolutionary prisoner's dilemma on different pairs of interaction and replacement networks. The relationship between these networks can be adjusted by the scale of interaction and reproduction, and the intensity of selection can be adjusted from the almost deterministic selection of the best strategy to the extremely stochastic selection. The evolutionary experiments showed that the larger scale of reproduction than the scale of interaction brought about higher level cooperation when the intensity of selection was high, and the minimum scale of interaction and reproduction was the best for the evolution of cooperation when the intensity of selection was low.
This papers proposes a novel self--adaptive scheme for the evolution of crucial control parameters in Evolutionary Algorithms. More specifically, we suggest to utilize the Differential Evolution algorithm to endemically evolve its own control parameters. To achieve this, two simultaneous instances of Differential Evolution are used, one of which is responsible for the evolution of the crucial user--defined mutation and recombination constants. This self--adaptive Differential Evolution algorithm alleviates the need of tuning these user--defined parameters while maintains the convergence properties of the original algorithm. The evolutionary self--adaptive scheme is evaluated through several well--known optimization benchmark functions and the experimental results indicate that the proposed approach is promising.
In this paper we study expressiveness of evolutionary computation. To do that we introduce evolutionary automata and define their several subclasses. To our surprise, we got the result that evolving finite automata by finite automata leads outside its class, and allows to express for example pushdown automata or Turing machines. This explains partially why Larry Fogel restricted representation in Evolutionary Programming to finite state machines only. The power of evolution is enormous indeed!
Network-on-chip (NoC) are considered the next generation of communication infrastructure, which will be omnipresent in most of industry, office and personal electronic systems. In platform-based methodology, an application is implemented by a set of collaborating intellectual properties (IPs) blocks. In this paper, we use two multi-objective evolutionay algorithms to address the problem of selecting the most adequate set of IPs (from an available library) that best implements the application. The IP selection optimization is driven by the minimization of hardware area, total execution time and power consumption.
In the fields of image processing and recognition, image segmentation is an important basic technique in which an image is partitioned into multiple regions (sets of pixels). In this paper, we propose a method for evolutionary image segmentation based on multiobjective clustering. In this method, two objectives, overall deviation and edge value, are optimized simultaneously using a multiobjective evolutionary algorithm. These objectives are important factors for image segmentation. The proposed method finds various solutions (image segmentation results) by the use of an evolutionary process. We apply the proposed method to several image segmentation problems and confirm that various solutions are obtained. In addition, we use a simple heuristic method to select one solution from the original Pareto solutions and show that a good image segmentation result is selected.
In future massively distributed service-based computational systems, resources will span many locations, organisations and platforms. In such systems, the ability to allocate resources in a desired configuration, in a scalable and robust manner, will be essential. We build upon a previous evolutionary market-based approach to achieving resource allocation in decentralised systems, by considering heterogeneous providers. In such scenarios, providers may be said to value their resources differently. We demonstrate how, given such valuations, the outcome allocation may be predicted. Furthermore, we describe how the approach may be used to achieve a stable, uneven load-balance of our choosing. We analyse the system's expected behaviour, and validate our predictions in simulation. Our approach is fully decentralised; no part of the system is weaker than any other. No cooperation between nodes is assumed; only self-interest is relied upon. A particular desired allocation is achieved transparently to users, as no modification to the buyers is required.
In this paper, we proposed an improved multi-objective evolutionary clustering approach (EMCOC) to resolve the overlapping problems in complex shape data. At present, most of the existing evolutionary clustering techniques fail to detect complex/spiral-shaped clusters. In our previous works [1], [2], we proposed several evolutionary multi-objective clustering algorithms and achieved promising results. However, they also suffer from this usual problem exhibited by evolutionary and unsupervised clustering approaches. Experimental results based on several artificial and real-world data show that the proposed EMCOC can successfully identify overlapping clusters. It also succeeds obtaining non-dominated and near-optimal clustering solutions in terms of different cluster quality measures and classification performance. The superiority of the EMCOC over some other multi-objective evolutionary clustering algorithms is also confirmed by the experimental results.
In order to design a multi-agent system with required emergent phenomena, evolutionary optimization can be used. The downside of this approach is large time needed to perform optimization due to the simulation of the multi-agent system that has to be carried out every time fitness function is evaluated. In the case when a single simulation result is not reliable, more than one simulation has to be executed for a fitness value evaluation, which is even more time-consuming. The research presented in this paper investigates improvements of evolutionary optimization of multi-agent systems when multiple simulations of the system are needed for fitness function evaluation. The improvement is based on a heuristic method for multi-agent system fitness evaluation. The proposed method considerably enhances fitness evaluation reliability by taking into account simulations completed in previous generations. For that reason the multiple simulations fitness value is constructed gradually over many generations, whereas a heuristic function is used for leveling fitness values based on a different number of multi-agent system simulations. The experimental results show that proposed method improves results of evolutionary optimization of emergent phenomena in multi-agent systems compared to the standard method, where a fitness function is evaluated based on a single system simulation, while using virtually the same execution time for the optimization process.
This paper presents an evolutionary programming with an ensemble of memories to deal with optimization problems in dynamic environments. The proposed algorithm modifies the classical evolutionary programming by applying a differential evolution step to the best individual as well as using a simulated-annealing-like dynamic strategy parameter. Diversity of the population is enhanced by an ensemble of external archives that serves as short-term and long-term memories. The archive members also serve as the basic solutions when environmental changes occur. The algorithm is tested on a set of 6 multimodal problems with a total of 49 change instances provided by CEC 2009 Competition on Evolutionary Computation in Dynamic and Uncertain Environments and the results are presented.
In this paper we present the development of a new self-reconfigurable robotic platform for performing on-line and on-board evolutionary experiments. The designed platform can work as an autonomous swarm robot and can undergo collective morphogenesis to actuate in different morphogenetic structures. The platform includes a dedicated power management, rich sensor mechanisms for on-board fitness measurement as well as very powerful distributed computational system to run learning and evolutionary algorithms. The whole development is performed within several large European projects and is open-hardware and open-software.
This study is motivated by the need to support concept selection under conflicting objectives. A recent idea concerning concept-based relaxed-Pareto-optimality is employed to develop a 'soft' evolutionary search approach. The proposed method allows set-based conceptual solutions, with performances close to those of the concept-based Pareto-optimal set, to survive the evolutionary search process. This allows designers, which are engaged in concept selection to examine not only the Pareto-optimal solutions from the different concepts. The relaxed-optimality exposes, within a desired performance resolution, other particular solutions of interest in concept selection. The proposed numerical solution approach involves a modification of NSGA-II to meet the needs of solving the described problem. The suggested algorithm is demonstrated using both an academic test function and a conceptual path planning problem.
An evolutionary synthesis method to generate impedance matching networks with low sensitivity is presented. The method uses a chromosome coding scheme based on the graph adjacency matrix representation. The efficiency of the proposed algorithm is tested in the synthesis of an impedance network for a monopole whip antenna and the results are compared with other examples found in the literature.
Automatic protein structure predictors use the notion of energy to guide the search towards good candidate structures. The energy functions used by the state-of-the-art predictors are defined as a linear combination of several energy terms designed by human experts. We hypothesised that the energy based guidance could be more accurate if the terms were combined more freely. To test this hypothesis, we designed a genetic programming algorithm to evolve the protein energy function. Using several different fitness functions we examined the potential of the evolutionary approach on a set of candidate structures generated during the protein structure prediction process. Although our algorithms were able to improve over the random walk, the fitness of the best individuals was far from the optimum. We discuss the shortcomings of our initial algorithm design and the possible directions for further research.
This work will evaluate three evolutionary algorithms in a constraint satisfaction problem. Specifically, the problem is the Eternity II, a edge-matching puzzle with 256 unique square tiles that have to be placed on a square board of 16 x 16 cells. The aim is not to completely solve the problem but satisfy as many constraints as possible. The three evolutionary algorithms are: genetic algorithm, a own implementation of a technique based on immune system concepts and a multiobjective evolutionary algorithm developed from the genetic algorithm. In addition to comparing the results obtained by applying these evolutionary algorithms, they also will be compared with an exhaustive search algorithm (backtracking) and random search. For the evolutionary algorithms two different fitness functions will be used, the first one as the score of the puzzle and the second one as a combination of the multiobjective algorithm objectives. We also used two ways to create the initial population, one randomly and the other with some domain information.
This is the second study exploring the creation of evolved art through evolutionary control of a dynamical system. Here 1-dimensional cellular automata rules are evolved to exhibit slow but persistent growth or to undergo planned senescence. These simple constraints encourage the automata to develop complex and visually pleasing behavior. Isotropic automata with a forced quiescent state are used, with rules evolved using a simple string representation; the fitness landscapes for both fitness functions are found to be quite rugged with many local optima. This is a desirable feature in an evolved art system as it yields a rich variety of outputs for the artist to use as image elements. A parameter study is performed and it is found that optimization of the slow-growth fitness function favors the use of large populations.
Legged robots show promise for complex mobility tasks, such as navigating rough terrain, but the design of their control software is both challenging and laborious. Traditional evolutionary algorithms can produce these controllers, but require manual decomposition or other problem simplification because conventionally-used direct encodings have trouble taking advantage of a problem's regularities and symmetries. Such active intervention is time consuming, limits the range of potential solutions, and requires the user to possess a deep understanding of the problem's structure. This paper demonstrates that HyperNEAT, a new and promising generative encoding for evolving neural networks, can evolve quadruped gaits without an engineer manually decomposing the problem. Analyses suggest that HyperNEAT is successful because it employs a generative encoding that can more easily reuse phenotypic modules. It is also one of the first neuroevolutionary algorithms that exploits a problem's geometric symmetries, which may aid its performance. We compare HyperNEAT to FT-NEAT, a direct encoding control, and find that HyperNEAT is able to evolve impressive quadruped gaits and vastly outperforms FT-NEAT. Comparative analyses reveal that HyperNEAT individuals are more holistically affected by genetic operators, resulting in better leg coordination. Overall, the results suggest that HyperNEAT is a powerful algorithm for evolving control systems for complex, yet regular, devices, such as robots.
Embedded systems require fault-tolerant circuitry if they are going to survive in harsh environments over extended time periods. Two approaches to evolving fault-tolerant digital circuitry have been proposed. In the population-based method circuits that perform well in the presence of specific faults are extracted from an evolving population. In the correlation based method circuits that exhibit different fault patterns are extracted and a majority voter determines the final behavior. In this paper we compare the two fault-tolerant methods using a 2 × 3 binary multiplier circuit as the test case.
The paper proposes a hypernetwork-based method for stock market prediction through a binary time series problem. Hypernetworks are a random hypergraph structure of higher-order probabilistic relations of data. The problem we tackle concerns the prediction of price movements (up/down) on stock markets. Compared to previous approaches, the proposed method discovers a large population of variable subpatterns, i.e. local and global patterns, using a novel evolutionary hypernetwork. An output is obtained from combining these patterns. In the paper, we describe two methods for assessing the prediction quality of the hypernetwork approach. Applied to the Dow Jones Industrial Average Index and the Korea Composite Stock Price Index data, the experimental results show that the proposed method effectively learns and predicts the time series information. In particular, the hypernetwork approach outperforms other machine learning methods such as support vector machines, naive Bayes, multilayer perceptrons, and k-nearest neighbors.
In this paper we present a model which allows to co-evolve the morphology and the control system of realistically simulated robots (creatures). The method proposed is based on an artificial ontogenetic process in which the genotype does not specify directly the characteristics of the creatures but rather the growing rules that determine how an initial artificial embryo will develop on a fully formed individual. More specifically, the creatures are generated through a developmental process which occurs in time and space and which is realized through the progressive addition of both structural parts and regulatory substances which affect the successive course of the morphogenetic process. The creatures are provided with a distributed control system made up of several independent neural controllers embedded in the different body parts which only have access to local sensory information and which coordinate through the effects of physical actions mediated by the external environment through the emission/detection of signals which diffuse locally in space. The analysis of evolved creatures shows how they display effective morphology and control mechanisms which allow them to walk effectively and robustly both on regular and irregular terrains in all the replications of the experiment. Moreover, the obtained results show how the possibility to develop such skills can be improved by also selecting individuals on the basis of a task-independent component which reward them for the ability to coordinate the movements of their parts.
In this paper, we use Genetic Programming (GP) to define a set of transforms on the space of greyscale images. The motivation is to allow an evolutionary algorithm means of transforming a set of image patterns into a more classifiable form. To this end, we introduce the notion of a Transform-based Evolvable Feature (TEF), a moment value extracted from a GP-transformed image, used in a classification task. Unlike many previous approaches, the TEF allows the whole image space to be searched and augmented. TEFs are instantiated through Cartesian Genetic Programming, and applied to a medical image classification task, that of detecting muscular dystrophy-indicating inclusions in cell images. It is shown that the inclusion of a single TEF allows for significantly superior classification relative to predefined features alone.
Two variants of cell model, namely eukaryotic, (containing a nucleus) and prokaryotic (without a nucleus) are compared in this research. The comparison looks at their relative evolvability and ability to integrate external environmental stimulus to direct protein pattern formation within a single cell. To the author's knowledge there has been no reported work comparing the relative performance of eukaryotic and prokaryotic artificial cells models. We propose a novel system of protein translocation for eukaryotic cells based on the process of nucleocytoplasmic transport observed in biological cells. Our results demonstrate that both cells are equally capable of integrating external environmental information to direct development. Furthermore we observe a higher degree of plasticity in eukaryotic cell models compared with prokaryotic
Despite their success as optimization methods, evolutionary algorithms face many difficulties to design artifacts with complex structures. According to paleontologists, living organisms evolved by opportunistically co-opting characters adapted to a function to solve new problems, a phenomenon called exaptation. In this paper, we draw the hypotheses (1) that exaptation requires the presence of multiple selection pressures, (2) that Pareto-based multi-objective evolutionary algorithms (MOEA) can create such pressures and (3) that the modularity of the genotype is a key to enable exaptation. To explore these hypotheses, we designed an evolutionary process to find the structure and the parameters of neural networks to compute a Boolean function with a modular structure. We then analyzed the role of each component using a Shapley value analysis. Our results show that: (1) the proposed method is efficient to evolve neural networks to solve this task; (2) genotypic modules and multiple selections gradients needed to be aligned to converge faster than the control experiments. This prominent role of multiple selection pressures contradicts the basic assumption that underlies most published modular methods for the evolution of neural networks, in which only the modularity of the genotype is considered.
A hyperheuristic is a high level problem solving methodology that performs a search over the space generated by a set of low level heuristics. One of the hyperheuristic frameworks based on a single point search consists of two main stages: heuristic selection and move acceptance. Most of the existing move acceptance methods compare a new solution, generated after applying a heuristic, against a current solution in order to decide whether to reject it or replace the current one. Late Acceptance Strategy is presented as a promising iterative local search methodology based on a novel move acceptance method. This method performs a comparison between the new candidate solution and a previous solution that is generated L steps earlier for acceptance. In this study, the performance of a set of hyper-heuristics utilising different heuristic selection methods combined with the Late Acceptance Strategy are investigated over an examination timetabling problem. The results illustrate the potential of this approach as a hyper-heuristic component. The hyper-heuristic formed by combining a random heuristic selection with Late Acceptance Strategy improves on the best results obtained in a previous study.
The performances (success) of a hill climber (RMHC) and a genetic algorithm (upGA) on a set of test problems with varied structural characteristics are compared to learn whether problem structural characteristic can be a feasible solution-independent indicator of when a problem will be more easily solved by a genetic algorithm than by hill climbing. Evidence supporting this hypothesis is found in this initial study. In particular, other factors (modularity, transitivity and fitness distribution) being equal, highly modular problems with broad right-skewed degree distributions are more easily solved by upGA than by RMHC. Suggestions are made for further research in this direction.
The goal of Adaptive Operator Selection is the on-line control of the choice of variation operators within Evolutionary Algorithms. The control process is based on two main components, the credit assignment, that defines the reward that will be used to evaluate the quality of an operator after it has been applied, and the operator selection mechanism, that selects one operator based on some operators qualities. Two previously developed Adaptive Operator Selection methods are combined here: Compass evaluates the performance of operators by considering not only the fitness improvements from parent to offspring, but also the way they modify the diversity of the population, and their execution time; Dynamic Multi-Armed Bandit proposes a selection strategy based on the well-known UCB algorithm, achieving a compromise between exploitation and exploration, while nevertheless quickly adapting to changes. Tests with the proposed method, called ExCoDyMAB, are carried out using several hard instances of the Satisfiability problem (SAT). Results show the good synergetic effect of combining both approaches.
Abstract—We present a computational model of human eye movements based on a genetic algorithm (GA). The model can generate elemental raw eye movement data in a four-second eye viewing window with a 25 Hz sampling rate. Based on the physiology and psychology characters of human vision system, the fitness function of the GA model is constructed by taking into consideration of five factors including the saliency map, short time memory, saccades distribution, Region of Interest (ROI) map, and a retina model. Our model can produce the scan path of a subject viewing an image, not just several fixations points or artificial ROI's as in the other models. We have also developed both subjective and objective methods to evaluate the model by comparing its behavior with the real eye movement data collected from an eye tracker. Tested on 18 (9 × 2) images from both an obvious-object image group and a non-obvious-object image group, the subjective evaluations shows very close scores between the scan paths generated by the GA model and those real scan paths; for the objective evaluation, experimental results show that the distance between GA's scan paths and human scan paths of the same image has no significant difference by a probability of 78.9% on average.
Particle Swarm Optimiszation (PSO) is a relatively new evolutionary computation technique compared to the more established ones like Genetic Algorithms, Evolution Strategies and Genetic Programming. In this study, a new parameter referred to as the spread factor is introduced so as to speed up the PSO convergence. This factor continuously modifies the inertia weight of the PSO velocity equation during the search process by measuring the distribution of particles around the global best particle. Test results show that the spread factor enables the PSO to achieve a good balance between exploration and exploitation. Consequently, escape from local optima and fast convergence to global optima can be guaranteed. This is due to the ability of the algorithm to maintain the search momentum especially when some particles are trapped at local optima, and to expedite convergence once all particles are within the vicinity of the global optima. The test results presented here illustrate the improvement of this adaptive approach over methods using either fixed or linearly decreasing inertia weights.
We investigate the effects of communication failures in grid-based, distributed genetic algorithms with various topologies. We evaluated the performance behavior of distributed GAs under varying levels of persistent communication failures, using the sorting network problem as a benchmark application. In this experiment, we find that distributed GA with larger population size is less affected by the lower communication failure rate. However, the effect of lower communication failure on the performance of distributed GA varies with the topologies when population size is small. For all the tree topologies we investigated, when communications failures occur extremely frequently, then a significant performance degradation is observed. However, even in these extreme cases, we show that simple retry/reroute protocols for recovering from communication failure are sufficient to recover most of the performance.
A new symbolic algorithm for multi-objective optimisation problems is proposed. It finds Pareto optimal solutions as equations of the dual Lagrange multipliers for continuous, differentiable, pseudoconvex, and convex functions. The algorithm is able to find the relationship between the decision variables that form the exact curve of the Pareto front.
An evolutionary approach has been proposed to improve Simplified Fuzzy ARTMAP neural network performance for off-line font-based recognition of Persian alphabetical characters. Some of Persian characters are so similar to each other. We have defined and used some fuzzy sets in feature extraction to improve recognition of these characters. Also, the presentation order of training patterns to a simplified fuzzy ARTMAP neural network affects the classification performance. The common method to solve this problem is to use several simulations with training patterns presented in random order, where voting strategy is used to compute the final performance. In this paper, a method based on Particle Swarm Optimization is proposed to obtain the presentation order of training Persian fonts for improving the performance of Simplified Fuzzy ARTMAP. This method uses generalization error as a criterion to specify the best order of training patterns in this problem. The new method has the advantage of improved classification performance compared to the random ordering.The achieved average recognition rates were 91.24% for twelve popular Persian fonts.
The model for the biologically inspired agent-based computation systems EMAS and iEMAS conformed to BDI standard is presented. System dynamics was modeled as the stationary Markov chain. The space of states and transition functions were identified. The probability transition of the whole system is composed of the conditional transitions caused by the particular actions. Such a model allows for better understanding the behavior of the proposed complex systems as well as their limitations. Because no constraint for the total number of agents was introduced, the model express the behavior of maximum configuration of the systems. Therefore it plays the similar role to the SGA infinite population model introduced by Vose. The sample application of iEMAS to the difficult global optimization problem (optimization of the artificial neural network architecture) showing its efficiency was also attached.
Free Search Differential Evolution (FSDE) is a new, population-based meta-heuristic algorithm that is a hybrid of concepts from Free Search (FS), Differential Evolution (DE) and opposition-based learning. The performance of the proposed approach is investigated and compared with DE and one of the recent variants of DE when applied to ten benchmark functions. The experiments conducted show that FSDE provides excellent results with the added advantage of no parameter tuning.
Gaussian process model is an effective and efficient method for approximating a continuous function. However, its computational cost increases exponentially with the size of training data set. A very popular way to alleviate this shortcoming is to cluster the whole training data set into a number of small clusters and then a local model is built for each cluster. However, widely used crisp clustering might not be accurate in the boundary areas among different clusters. This paper proposes a fuzzy clustering based method for improving approximation quality. Several clusters with overlaps are firstly obtained by fuzzy C-means clustering and then local models are built for these clusters. It has been demonstrated that this method can be used with evolutionary algorithms for dealing expensive optimization problems.
In this paper, a fuzzy selection based differential evolution algorithm (FSBDE) for analog cell sizing is investigated. By combining selection based constraint handling method and fuzzy membership functions, a new selection methodology for handling fuzzy constraints is proposed and is integrated with the differential evolution (DE) algorithm to construct FSBDE. FSBDE specializes in solving analog sizing problems capturing human intentions, both avoiding inflexibility of crisp constraint sizing methods and the excessive relaxation of available fuzzy sizing approaches. The high optimization ability of the DE algorithm is also inherited in this approach. Comparisons are carried out with crisp selection based differential evolution algorithm (SBDE) and DE in conjunction with available fuzzy optimization method, showing that the proposed FSBDE algorithm presents important advantages in terms of fuzzy constraint handling ability and optimization quality.
Discovery of transcription factor binding sites (TFBSs) or DNA motifs in promoter regions of genes plays a key role in understanding the regulations of gene expression. In the past decade computational approaches, including evolutionary computation techniques, for searching for motifs have demonstrated good potential, and some results reported in literature are quite promising. Recently, some favorable progresses on evolutionary mining of motifs have been made and documented in GAME and GALF-P, where GAME employs a Bayesian-based scoring function and GALF-P aims to improve the algorithm performance with local filtering and adaptive post-processing. To improve discovering performance in terms of the recall, precision rates and algorithm reliability, this paper presents an alternative genetic algorithm termed as GAPK for resolving the problem of motifs discovery. In our proposed GAPK framework, a prior knowledge on motifs in a given dataset is used to initialize a population. Our technical contributions include a matrix representation for $-mers, a mismatch-based filtering method for search space reduction, a model mismatch score (MMS) as fitness function, new genetic operations and a model refinement processing. Some benchmarked datasets associated with eight transcription factors are used in our experiments. Comparative studies were carried out with well-known tools including GAME, GALF-P, MEME, MDScan and AlignACE. Results show that our method outperforms other techniques in terms of F-measure.
A novel parallel approach to run standard particle swarm optimization (SPSO) on Graphic Processing Unit (GPU) in a Personal Computer is presented in this paper. By using the general-purpose computing ability of GPU and based on the software platform of Compute Unified Device Architecture (CUDA), SPSO can be executed in parallel on GPU. Experiments are conducted by running SPSO both on GPU and CPU, respectively, to optimize four benchmark test functions. The running time of the SPSO based on GPU (GPU-SPSO) is greatly shortened compared to that of the SPSO on CPU (CPU-SPSO). Running speed of GPU-SPSO can be more than extbf{11} times as fast as that of CPU-SPSO, with the same performance. GPU-SPSO shows special speed advantages on large swarm population applications and hign dimensional problems, compared to CPU-SPSO, which will be widely used in real optimizing problems.
Polymorphic digital circuits contain ordinary and polymorphic gates. In the past, Cartesian Genetic Programming (CGP) has been applied to synthesize polymorphic circuits at the gate level. However, this approach is not scalable. Experimental results presented in this paper indicate that larger and more efficient polymorphic circuits can be designed by a combination of conventional design methods (such as BDD, Espresso or ABC System) and evolutionary optimization (conducted by CGP). Proposed methods are evaluated on two benchmark circuits -- Multiplier/Sorter and Parity/Majority circuits of variable input size.
The bacterial genome is well understood by biologists. Although its efficiency and adaptability should make it a good model for evolutionary algorithms, the bacterial genome is tightly coupled with the components of the bacterial metabolism, referred to here as the metabolome. This paper explores an approach to modelling an artificial bacterial metabolome in an efficient and modular manner, so that analogues of bacterial genome organisation and gene regulation can be implemented in evolutionary algorithms. We propose a particulate model of bacterial metabolic pathways in which the constituents drift in a fixed, limited space and obey a limited set of biologically plausible reaction rules. The potential of this model is demonstrated by creating a network that is capable of appropriate behavioural switching that can be observed in bacteria.
In this paper we show a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation approach must generate a new feasible set of tasks to be assigned to a crew member. Is is modeled as a shortest path with resource constraints problem in a graph, which can be virtually applied to all kinds of crew scheduling problems. The genetic algorithm is also general, and knowlege about specific problems may be incorporated. The hybrid algorithm is tested with instances from the literature and also with real instances, and the results show that the genetic algorithm is able to quickly generate most of the columns needed to solve the problem, while the exact method generates the last columns to find the optimal solution. The algorithm can also incorporate other kind of heuristics.
With the ever increasing volume of the digital data being generated from our day to day life there is a huge increase in the demand for much faster and denser storage technologies. Conventional two dimensional (surface) storage/memory technologies may soon be replaced with much faster and denser three dimensional volumetric (holographic) storage technologies. Photo sensitive protein Bacteriorhodopsin( BR) has been proven to have great chemical, thermal and holographic properties and is a good choice as a holographic material in volumetric memory design. Balanced modulated codes are used in volumetric memory systems to reduce the bit error rate (BER) and improve the fidelity, currently coding schemes like 6:8 balanced modulated coding are employed which limit the size of the page to 8-bits and acheive a code rate (utility) of 75%. As the volumetric storage technology matures we need efficient algorithms to produce balanced modulation codes with high code rate on bigger page sizes. In this paper we give new algorithms to generate balanced modulation codes which can achieve superior code rates compared to the existing methods to generate balanced modulated codes.
Time Related Association rule mining is a kind of sequence pattern mining for sequential databases. In this paper, we introduce a method of Generalized Association Rule Mining using Genetic Network Programming (GNP) with time series processing mechanism in order to find time related sequential rules efficiently. GNP represents solutions as directed graph structures, thus has compact structure and implicit memory function. The inherent features of GNP make it possible for GNP to work well especially in dynamic environments. GNP has been applied to generate time related candidate association rules as a tool using the database consisting of a large number of time related attributes. The aim of this algorithm is to better handle association rule extraction from the databases in a variety of time-related applications, especially in the traffic volume prediction problems. The generalized algorithm which can find the important time related association rules is described and experimental results are presented considering a traffic prediction problem.
An optimised schedule is vital for the operation of an interplanetary space mission. The scheduling problem of a mission with the scientific objective of reaching global coverage with more than one instrument is complex and highly restricted. Evolutionary algorithms can be an efficient method in solving scheduling problems and generating pareto-optimal alternatives. The application of a combined evolutionary algorithms including Evolutionary Strategy, Genetic Algorithms and Differential Evolution is demonstrated for a reference scenario of a low-orbit Moon mapping mission. A reduced set of restriction is taken into account for creating a master schedule for global coverage of three different instruments for the whole mission time. An optimal set of short term operation time lines for one orbit is generated, which can be combined to a complete mission schedule. The result shows that more than one year of the total mission time can be saved with an optimised schedule.
Genetic algorithms were among the early choices for quantum circuit synthesis, because of their ability to evolve a given starting circuit towards one of the possible solutions. The synthesis method presented here is the first GA-based approach that dynamically adjusts its control parameters. The adaptive parameter control takes into account the analysis performed on each genetic operator, in order to automatically find an acceptable tradeoff between runtime and appropriate exploration. The experimental results prove that this method improves the synthesis runtime and the size of the circuit to be handled up to 7 qubits (previous GA-based techniques are effective only for 3-4 qubit circuits).
This paper describes a successful combination of genetic algorithm and local search procedure to find good solutions for just-in-time job-shop scheduling problem with earliness and tardiness penalties. For each job is given a specific order of machines in which its operations must be processed, and each operation has a due date, a processing time, and earliness and tardiness penalties, which are paid if the operation is completed before or after its due date. The problem is very hard to solve to optimality even for small instances, but the proposed genetic algorithm were able to find good solutions for several instances tested, and very good results were obtained after submitting the solution found by the genetic algorithm to a local search procedure. The algorithms were tested with instances from the literature, with up to 20 jobs and 10 machines, and the results compared to those of a recently published paper that uses heuristics upon a lagragean relaxation of a mixed integer programming model, showing that the proposed algorithm can improve the solution value for most of the instances.
In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks (ANNs), genetic algorithms (GAs), particle swarm optimization (PSO), etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile ad hoc network (MANET), wireless sensor network (WSN), etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, that is, the network topology changes over time due to energy conservation or node mobility. Therefore, the SP problem turns out to be a dynamic optimization problem (DOP) in MANETs. In this paper, we propose to use elitism-based immigrants GA (EIGA) to solve the dynamic SP problem in MANETs. We consider MANETs as target systems because they represent new generation wireless networks. The experimental results show that the EIGA can quickly adapt to the environmental changes (i.e., the network topology change) and produce good solutions after each change.
This paper presents a novel classification approach that integrates fuzzy classification rules and Genetic Network Programming (GNP). A fuzzy discretization technique is applied to transform the dataset, particularly for dealing with quantitative attributes. GNP is an evolutionary optimization technique that uses directed graph structures as genes instead of strings and trees of Genetic Algorithms (GA) and Genetic Programming (GP), respectively. This feature contributes to creating quite compact programs and implicitly memorizing past action sequences. Therefore, in the proposed method, taking the GNP's structure into account 1) extraction of fuzzy classification rules is done without identifying frequent itemsets used in most Apriori-based data mining algorithms, 2) calculation of the support, confidence and x2 value is made in order to quantify the significance of the rules to be integrated into the classifier, 3) fuzzy membership values are used for fuzzy classification rules extraction, 4) fuzzy rules are mined through generations and stored in a general pool. On the other hand, parameters of the membership functions are evolved by non-uniform mutation in order to perform a more global search in the space of candidate membership functions. The performance of our algorithm has been compared with other relevant algorithms and the experimental results have shown the advantages and effectiveness of the proposed model.
Genetic Network Programming (GNP) is a newly proposed evolutionary approach which can evolve itself and find the optimal solutions. It is a novel method based on the idea of Genetic Algorithm (GA) and uses the data structure of directed graphs. As GNP has been developed for dealing with problems in dynamic environments, many papers have demonstrated that GNP can be applied to many areas such as data mining, forecasting stock markets, elevator control systems, etc. Focusing on GNP's distinguished expression ability of the graph structure, this paper proposes a method named Genetic Network Programming with Reconstructed Individuals (GNP with RI). In the proposed method, the worst individuals are reconstructed and enhanced by the elite information before undergoing genetic operations (mutation and crossover). The enhancement of worst individuals mimics the maturing phenomenon in nature, where bad individuals can become smarter after receiving good education. GNP with RI has been applied to the tile-world which is an excellent bench mark for evaluating the proposed architecture. The performance of GNP with RI is compared with conventional GNP demonstrating its superiority.
Genetic Network Programming (GNP) is an evolutionary algorithm derived form GA and GP. It can deal with complex problems in dynamic environments efficiently and effectively because of its directed graph structure, reusability of nodes, and implicit memory function. This paper proposed a new method to optimize GNP algorithm by strengthening its exploitation ability through extracting and using rules. In the former research, the order of judgment node chain is ignored. The basic idea of GNP with Rule Accumulation Considering Judgment Order (GNP with RA) is to extract rules with order having high fitness values from each individual and store them in the pool every generation. A rule is defined as a sequence of successive judgment results and a processing node, which represents the good experiences of the past behaviors. As a result, the rule pool serves as an experience set of GNP obtained in the evolution process. By extracting the rules during the evolution period and then matching them with the situations of the environment, we could guide agents' behavior properly and get better performance of the agents. In this paper, GNP with RA is applied to the problem of determining agents' behaviors and Tile-world was used as the simulation environment in order to evaluate its effectiveness. The simulation results demonstrate that GNP with RA could have better performances than the conventional GNP method both in the average fitness value and stability.
Conventional genetic programming (GP) does not guarantee no revisits, i.e., a program may be generated for fitness evaluations more than one time. This is clearly wasteful in applications that involve expensive and/or time consuming fitness evaluations. This paper proposes a new GP – non-revisiting genetic programming NrGP – that guarantees that all programs generated is original. The basic idea is to use memory to store all programs generated. To increase efficiency in indexing and storage, the memory is organized as an S-expression trie. Since the number of solutions generated is modest for applications involving expensive and/or time consuming fitness evaluations, the extra memory needed is manageable. GP and NrGP are compared using two GP bench mark problems, namely, the symbolic regression and the even N-parity problem. It is found that NrGP outperforms GP, significantly reducing the computational effort (CE) required. This clearly shows the power of the idea of ensuring no revisits. It is anticipated that the same non-revisiting idea can be applied to other types of GP to enhance their efficiency. A new CE measurement is also reported that removes some statistical biases associated with the conventional CE.
A new cellular model for evolving stable, lightweight structures is presented in this paper. The focus lies in enhancing the ability of the cellular system to create complex 3D shapes with non self-similar regions. Compared to our previous work~\cite{Steiner08}, the model proposed in this paper is composed of polarized cells that have directionally differential force functions for cell adhesion and thus are able to follow morphogen gradients (chemotaxis). We investigate the evolution of global information in form of evolving morphogen gradients that are created prior to development, which serve to guide cellular and shape differentiation. 0 Our analysis shows that for a set of Pareto-optimal solutions of lightweight stable structures, no unique gradient can be evolved. Nevertheless, it is revealed that neighboring individuals in the genotype space are also neighbored in the gradient space. By contrast, neighborhood in the fitness space is not maintained in the genotype space. These results suggest that a hierarchical genetic formulation might be better than a 'common predefined spatial pattern' in form of a predefined gradient. In addition, our analysis also implies that some well-known properties in direct-coding evolutionary algorithms may be lost in developmental mappings.
Glomerulus is the filtering unit of the kidney. In the computer aided diagnosis system designed for kidney disease, glomerulus extraction is an important step for analyzing kidney-tissue image. Against the disadvantages of traditional methods, this paper proposes a glomerulus extraction method using genetic algorithm for edge patching. Firstly, Canny edge detector is applied to get discontinuous edges of glomerulus. After labeling to remove the noises, genetic algorithm is used to search for optimal patching segments to join those edges together. Lastly, the edges and the patching segments with high fitness would be able to form the whole edge of the glomerulus. Experiments and comparisons indicate the proposed method can extract the glomerulus from kidney-tissue image both fast and accurately.
The role of gradient estimation in global optimization is investigated. The concept of a regional gradient is introduced as a tool for analyzing and comparing different types of gradient estimates. The correlation of different estimated gradients to the direction of the global optima is evaluated for standard test functions. Experiments quantify the impact of different gradient estimation techniques in two population-based global optimization algorithms: fully-informed particle swarm (FIPS) and multiresolutional estimated gradient architecture (MEGA).
We present a grammar-based genetic programming framework for the solving the timetabling problem via the evolution of constructive heuristics. The grammar used for producing new generations is based on graph colouring heuristics that have previously proved to be effective in constructing timetables as well as different slot allocation heuristics. The framework is tested on a widely used benchmarks in the field of exam time-tabling and compared with highly-tuned state-of-the-art approaches. Results show that the framework is very competitive with other constructive techniques
L-systems are parallel generative grammars that can model branching structures. Taking a graphical object and attempting to derive an L-system describing it is a hard problem. Grammatical Evolution (GE) is an evolutionary technique aimed at creating grammars describing the legal structures an object can take. We use GE to evolve L-systems, and investigate the effect of elitism, and the form of the underlying grammar.
In this paper, we propose a new heuristics called 'group extinction'. The heuristics is inspired by the existence of the extinction in the nature that groups of individuals, which have been consuming a large amount of the ecological resources, are not always the best groups in the evolutionary process. Ideally, these groups should be forced to become extinct such that the resources they use can be released to the other individuals or groups. In the context of optimization, the motivation of using the group extinction is to reduce the computational resources used by groups of candidate solutions that do not have any significant contribution to the overall performances of the optimization algorithms. The proposed heuristics is tested in the well-known framework of evolution strategy and their performances on the common unimodal and multimodal optimization problems are investigated. Experimental results show that using the group extinction heuristics can significantly reduce the average numbers of function evaluations to reach the optima, in particular when large populations are used.
We present a model of multi-level selection. By this we mean the idea that there are multiple units of selection each of which operates on a different hierarchical level. Concretely we consider here a model of 3 hierarchical levels and various selection scenarios of adaptive conflict between levels. The main finding of this contribution is that in order for selection at higher level units to be effective, it has to occur at a high frequency compared to low level selection. From this we conclude that multi-level selection is biologically not very plausible.
This paper is concerned with a problem in information organization and retrieval within Web communities. Most work in this domain is focused on reputation-based systems which exploit the experience gathered by previous users in order to evaluate resources at the community level. The current research focuses on a slightly different approach: a personalized evaluation system whose goal is to build a flexible and easy way to manage resources in a personalized manner. The functionality of such a model comes from local trust metrics which propagate the trust to a limited level into the system and, finally, lead to the appearance of minorities sharing some similar features/preferences. A modified PSO procedure is designed in order to analyze such a system and, in conjunction with a simple agglomerative clustering algorithm, identify homogenous groups of users.
Particle swarm optimization (PSO) is a swarm intelligence technique originally inspired by models of flocking and of social influence that assumed homogeneous individuals. During its evolution to become a practical optimization tool, some heterogeneous variants have been proposed. However, heterogeneity in PSO algorithms has never been explicitly studied and some of its potential effects have therefore been overlooked. In this paper, we identify some of the most relevant types of heterogeneity that can be ascribed to particle swarms. A number of particle swarms are classified according to the type of heterogeneity they exhibit, which allows us to identify some gaps in current knowledge about heterogeneity in PSO algorithms. Motivated by these observations, we carry out an experimental study of two heterogeneous particle swarms each of which is composed of two kinds of particles. Directions for future developments on heterogeneous particle swarms are outlined.
The Hooke-Jeeves (HJ) Pattern Search, which seems to be the most popular choice among the local search algorithms, was used as an alternative to the dimensional local search (DLS), which has provided excellent results in previous work. In this paper, the question whether the well-known Hooke-Jeeves pattern search could outperform the DLS algorithm that was devised somewhat ad-hoc, is to be investigated. The Moving Peaks (MP) function is used as a benchmark. In our experiments, the algorithms performed almost identically well on the problem instances used. However, it was observed that the pattern move, an intrinsic part of the HJ algorithm, hardly contributed to the quality of the outcome, in fact less than the number sequence used as step sizes for both local searches. We provide some investigations into why the pattern move is less successful than most authors – including the original inventors of the Hooke-Jeeves search – seem to anticipate.
Automatically synthesizing behaviors for robots with articulated bodies poses a number of challenges beyond those encountered when generating behaviors for simpler agents. One such challenge is how to optimize a controller that can orchestrate dynamic motion of different parts of the body at different times. This paper presents an incremental shaping method that addresses this challenge: it trains a controller to both coordinate a robot's leg motions to achieve directed locomotion toward an object, and then coordinate gripper motion to achieve lifting once the object is reached. It is shown that success is dependent on the order in which these behaviors are learned, and that despite the fact that one robot can master these behaviors better than another with a different morphology, this learning order is invariant across the two robot morphologies investigated here. This suggests that aspects of the task environment, learning algorithm or the controller dictate learning order more than the choice of morphology.
In this study, we intorduce a hybrid immune algorithm based on the intelligent recombination operator and clonal selection algorithm. The intelligent recombination operator uses orthogonal experimental design for factor analysis which identifies the potentially gene segments from two individuals to improve their affinities. The new algorithm, termed as Hybrid Immune Algorithm with Recombination (HIAR), can avoid the decrease of gene diversity in evolutionary process. It evaluates the hamming distance before recombination and uses the two individuals which have the largest hamming distance between each other to implement intelligent recombination operator. It is shown empirically that HIAR has better performance in solving benchmark functions as compared with Intelligent Evolutionary Algorithm and Clonal Selection Algorithm.
A novel hybrid multiobjective estimation of distribution algorithm is proposed in this study. It combines an estimation of distribution algorithm based on local linear embedding and an immune inspired algorithm. According to [1], Pareto set to the continuous multiobjective optimization problems, in the decision space, is a piecewise continuous (m-1)-dimensional manifold, where m is the number of objectives. By this regularity, a local linear embedding based manifold algorithm is introduced to build the distribution model of promising solutions. Besides, for enhancing local search ability of the EDA, an immune inspired sparse individual clone algorithm (SICA) is introduced and combined with the EDA. The novel hybrid multiobjective algorithm, named HMEDA, is proposed accordingly. Compared with three other state-of-the-art multiobjective algorithms, this hybrid algorithm achieves comparable results in terms of convergence and diversity. Besides, the tradeoff proportions of EDA to SICA in HMEDA are studied. Finally, the scalability to the number of decision variables of HMEDA is investigated.
Incorporating different kinds of micro-theories of cognition and modulating several mechanisms to unify all the recommended actions and outputs of an Intelligent System when a huge amount of environmental variables are changing continuously with increasing complexity, may become a very comprehensive task. The presented framework proposes an Hybrid Cognitive Architecture that relies on integrating of emergent systems approaches —connectionist, enactive and autopoietic systems—, and cognitivist approaches, in order to combine implicit and explicit processes necessary in developing cognitive skills. The proposed architecture includes different kinds of learning capabilities at each cognitive level which grant to the architecture a big plasticity. In addition, the propounded attention module includes an evolutionary mechanism based on gene expression programming to evolve a set of eligibility conditions in charge of modulating the coalition/ subordination of specialized behaviours, taking into consideration the theatre metaphor for consciousness. Finally, a co-evolutionary mechanism is proposed to propagate behaviours and knowledge between intelligent systems —Agents— on the basis of memetic engineering. The proposed architecture was proved in an robotic simulated environment using a multi-agent platform where several emergent properties of self-organization arose.
This paper introduces a new vector evaluated multi-objective optimization algorithm. The vector evaluated differential evolution particle swarm optimization (VEDEPSO) algorithm is a hybridization of the classical vector evaluated particle swarm optimization (VEPSO) and vector evaluated differential evolution (VEDE) algorithms of Parsopoulos et. al. [9], [10]. Comparisons of VEDEPSO with respect to VEPSO and VEDE on a well known multi-objective benchmark problem set indicated that significant performance improvements can be attributed to the VEDEPSO algorithm.
The population-based incremental learning (PBIL) algorithm is a combination of evolutionary optimization and competitive learning. Recently, the PBIL algorithm has been applied for dynamic optimization problems. This paper investigates the effect of the learning rate, which is a key parameter of PBIL, on the performance of PBIL in dynamic environments. A hyper-learning scheme is proposed for PBIL, where the learning rate is temporarily raised whenever the environment changes. The hyper-learning scheme can be combined with other approaches, e.g., the restart and hypermutation schemes, for PBIL in dynamic environments. Based on a series of dynamic test problems, experiments are carried out to investigate the effect of different learning rates and the proposed hyper-learning scheme in combination with restart and hypermutation schemes on the performance of PBIL. The experimental results show that the learning rate has a significant impact on the performance of the PBIL algorithm in dynamic environments and that the effect of the proposed hyper-learning scheme depends on the environmental dynamics and other schemes combined in the PBIL algorithm.
In this paper we describe simulation of autonomous robots controlled by recurrent neural networks, which are evolved through indirect encoding using HyperNEAT algorithm. The robots utilize 180 degree wide sensor array. Thanks to the scalability of the neural network generated by HyperNEAT, the sensor array can have various resolution. This would allow to use camera as an input for neural network controller used in real robot. The robots were simulated using software simulation environment. In the experiments the robots were trained to drive with imaximum average speed. Such fitness forces them to learn how to drive on roads and avoid collisions. Evolved neural networks show excellent scalability. Scaling of the sensory input breaks performance of the robots, which should be gained back with re-training of the robot with a different sensory input resolution.
This paper proposes an idea of approximating the hypervolume of a non-dominated solution set using a number of achievement scalarizing functions with uniformly distributed weight vectors. Each achievement scalarizing function with a different weight vector is used to measure the distance from the reference point of the hypervolume to the attainment surface of the non-dominated solution set along its own search direction specified by its weight vector. Our idea is to approximate the hypervolume by the average distance from the reference point to the attainment surface over a large number of uniformly distributed weight vectors (i.e., over various search directions). We examine the effect of the number of weight vectors (i.e., the number of search directions) on the approximation accuracy and the computation time of the proposed approach. As expected, experimental results show that the approximation accuracy is improved by increasing the number of weight vectors. It is also shown that the proposed approach needs much less computation time than the exact hypervolume calculation for a six-objective knapsack problem even when we use about 100,000 weight vectors.
We have studied the use of cellular automata and cellular genetic algorithms for the image classification and ordering problems. The cellular genetic algorithm is a genetic algorithm that has similarities with cellular automata. Image distances are measured as a number of needed cellular GA transforms, when morphing from image to image. Images distances are given to the traveling salesman solver, which orders the images to the shortest route order. The preliminary results seem to support the hypothesis that in principle this kind of image ordering and classification method works. The drawback of the proposed method is a large amount of calculations and the needed when we are testing each image against every other image. Independent component analysis is used in order to construct 3D model of how the tested images are located in space relative to each other.
RNA has important structural, functional, and regulatory parts in the cell as well as a critical role in multiple stages of protein synthesis. An RNA molecule's shape largely determines its function in an organic system. Accordingly, computational RNA structural prediction methods are of significant interest. For ab initio cases where only an RNA sequence is known, structure prediction techniques typically employ free energy minimization of a given RNA molecule via a thermodynamic model. Unfortunately, the minimum free energy structure is rarely the native structure. This is thought to be due to errors in the experimentally determined thermodynamic model parameters. RnaPredict is an evolutionary algorithm designed for the prediction of RNA secondary structure; it currently utilizes the stacking-energy thermodynamic models INN and INN-HB. The effect of an enhanced model, efn2, on RnaPredict is investigated. The efn2 model significantly improved the sensitivity and specificity of the majority of structures evaluated.
In this paper, a revised form of Implicit Context Representation Cartesian Genetic Programming is used in the development of a diagnostic tool for the assessment of patients with neurological dysfunction such as Alzheimer's disease. Specifically, visuo-spatial ability is assessed by analysing subjects' digitised responses to a simple figure copying task using a conventional test environment. The algorithm was trained to distinguish between classes of visuo-spatial ability based on responses to the figure copying test by 7--11 year old children in which visuo-spatial ability is at varying stages of maturity. Results from receiver operating characteristic (ROC) analysis are presented for the training and subsequent testing of the algorithm and demonstrate this technique has the potential to form the basis of an objective assessment of visuo-spatial ability.
In Genetic Algorithms (GAs) technique, offspring chromosomes are created by merging two parent chromosomes using a crossover operator or modifying an existing chromosome using a mutation operator. However, in scheduling problems in which the genes represent activities' start times, the crossover and mutation operators may cause violation of the precedence relationships in the offspring chromosomes. This paper proposes improved crossover and mutation algorithms to directly devise feasible offspring chromosomes. The proposed algorithms employed the traditional Free Float (FF) and a newly-introduced Backward Free Float (BFF). The obtained results exhibited robustness of the proposed algorithms to reduce the computational costs, and high effectiveness to search for optimal solutions. Moreover, validation was performed by comparing the results against the exact solutions obtained by the Integer Programming (IP) technique.
Capacitated Arc Routing Problem (CARP) has attracted much interest because of its wide applications in the real world. Recently, a memetic algorithm proposed by Lacomme et al. (LMA) has been demonstrated to be a competitive approach to CARP. The crossover operation of LMA is carried out based on an implicit representation scheme, while it conducts local search on the basis of an explicit representation scheme. Hence, the search process of LMA involves frequent switch between the spaces defined by the two representation schemes. However, a good solution in one space is not necessarily good in the other. In this paper, we show that the local search process of LMA might be ineffective due to such reason, and suggest adopting a more careful way to coordinate the local search. As a result, two new local search methods are proposed, which resulted in two improved LMA (ILMA) algorithms. Experimental results on benchmark instances of CARP showed that the ILMA significantly outperformed LMA in terms of solution quality, and sometimes even in terms of computational time. Furthermore, ILMA improved the best known solutions for 8 problem instances out of the total 24 instances.
In the later period of optimization by particle swarm optimization (PSO) algorithm, the diversity scarcity of population easily causes the algorithm fall into the local optimum. Therefore, an improved PSO (IPSO) algorithm is presented, in which each particle has the ability of keeping its inertia motion and learning from another randomly selected particle with better performance; moreover, for the particle with better performance, the inertia weight will be larger and the learning coefficient will be smaller. Thus, for the particles sorted in order of decreasing performance, the inertia weights are decreased and the learning rate coefficients are increased gradually. The new learning approach develops the diversity of the population, while the new parameters setting approach develops the adaptability of the population. Comparison results with the basic PSO on the examination of some well-known benchmark functions show that the IPSO algorithm has higher searching speed and stronger global searching ability.
Shuffled frog leaping algorithm (SFLA) is mainly used for the discrete space optimization. For SFLA, the population is divided into several memeplexes, several frogs of each memeplex are selected to compose a submemeplex for local evolvement, according to the mechanism that the worst frog learns from the best frog in submemeplex or the best frog in population, and the memeplexes are shuffled for the global evolvement after some generations of each memeplex. Derived by the discrete SFLA, a new SFLA for continuous space optimization is presented, in which the population is divided based on the principle of uniform performance of memeplexes, and all the frogs participate in the evolvement by keeping the inertia learning behaviors and learning from better ones selected randomly. The simulation results of searching minima of several multi-peak continuous functions show that the improved SFLA can effectively overcome the problems of premature convergence and slow convergence speed, and achieve high optimization precision.
In conventional RBF Network structure, different layers perform different tasks. Hence, it is useful to split the optimization process of hidden layer and output layer of the network accordingly. This paper proposes RBF Network hybrid learning with Particle Swarm Optimization (PSO) for better convergence, error rates and classification results. RBF Network hybrid learning involves two phases. The first phase is a structure identification, in which unsupervised learning is exploited to determine the RBF centers and widths. This is done by executing different algorithms such as k-mean clustering and standard derivation respectively. The second phase is parameters estimation, in which supervised learning is implemented to establish the connections weights between the hidden layer and the output layer. This is done by performing different algorithms such as Least Mean Squares (LMS) and gradient based methods. The incorporation of PSO in RBF Network hybrid learning is accomplished by optimizing the centers, the widths and the weights of RBF Network. The results for training, testing and validation of five datasets (XOR, Balloon, Cancer, Iris and Ionosphere) illustrate the effectiveness of PSO in enhancing RBF Network learning compared to conventional Backpropogation.
The biclustering technique was developed to avoid some of the drawbacks presented by standard clustering techniques. Given that biclustering requires the optimization of at least two conflicting objectives and that multiple independent solutions are desirable as the outcome, a few multi-objective evolutionary algorithms for biclustering were proposed in the literature. However, apart from the individual characteristics of the biclusters that should be optimized during their construction, several other global aspects should also be considered, such as the coverage of the dataset and the overlap among biclusters. These requirements will be addressed in this work with the MOM-aiNet+ algorithm, which is an improvement of the original multi-objective multipopulation artificial immune network denoted MOM-aiNet. Here, the MOM-aiNet+ algorithm will be described in detail, its main differences from the original MOM-aiNet will be highlighted, and both algorithms will be compared, together with three other proposals from the literature.
In the course of neurobiological studies the following discovery has been made: Extracted rat nerve cells which show no physical connections start combining and connecting each other to functional, active networks without any further influence. During this process the interconnection of neighboring as well as more distant nerve cells to smaller or global networks is guaranteed by axonal growth. Furthermore, during the process of connecting and synchronizing of networks, the inactive synapses became active once, the cell function may be transfigured from a catalyzing to a blocking one, that allows the conclusion of axonal growth as being an important modifier and influence in the process. Considering the discoveries, the axonal growth needs to be followed and analyzed in order to draw more scientific and detailed conclusions about the self-organizational potentials of nerve cells, the focusing on blocking and catalyzing aspects and their importance for the development of independent networks. A software is needed which enables the scientists to evaluate the nerve cell connections and applicate a statistical analysis of axonal growth. The results of this analysis may be used to create a model which simulates the self-organizational abilities of biological networks. Herzog et al. 2007 proposes a usage of those models as templates for artificial neuronal networks displaying the biological aspects more detailed than the currently available models. In this work we present a axon segmentation algorithm, based on a fuzzy-controlled system. The problems that appear, is that a correct setting of the rule-set can hardly be known, so we prove to optimize the rule-set whith evolutionary algorithms.
Artificial Immune Recognition System (AIRS) is an immune inspired classifier that competes with famous classifiers. One of the most important components of AIRS is resource competition. The goal of resource competition is the development of the fittest individuals. Resource competition phase removes weakest individuals and selects strongest (seemly good) individuals. This type of selection has high selective pressure with a loss of diversity. It may generate premature memory cells and decrease the accuracy of classifier. In this study, the Real World Tournament Selection (RWTS) method is incorporated in resource competition phase of AIRS to prevent this issue and experiments are conducted to evaluate the accuracy of new algorithm (RWTSAIRS). The combination of cross validation and t test is used as evaluation method. Algorithms tested on benchmark datasets of the UCI machine learning repository show that RWTSAIRS obtained higher accuracy than AIRS in all cases and that the difference between accuracies of two algorithms was significant in majority of cases.
The effect of varying the number of offspring (broodsize) each pair of parents produces as a function of the degree of difference between parents is investigated. The children within each family, firstly compete with each other to see who will survive (sibling rivalry). Only then do they interact with the rest of the population. The idea is tested on three test functions that commonly appear in the literature on building blocks: the hierarchical if and only if HIFF function, a Royal Road function and a concatenated trap function. The simulations reveal a statistically significant reduction in the number of fitness evaluations required to find a global optimum.
Biological neurons are extremely complex cells whose morphology grows and changes in response to the external environment. Yet, artificial neural networks (ANNs) have represented neurons as simple computational devices. It has been evident for a long time that ANNs have learning abilities that are insignificant compared with some of the simplest biological brains. We argue that we understand enough neuroscience to create much more sophisticated models. In this paper, we report on our attempts to do this.We identify and evolve seven programs that together represents a neuron which grows post evolution into a complete 'neurological' system. The network that occurs by running the programs has a highly dynamic morphology in which neurons grow, and die, and neurite branches together with synaptic connections form and change. We have evaluated the capability of these networks for playing the game of checkers. Our method has no board evaluation function, no explicit learning rules and no human expertise at playing checkers is used. The learning abilities of these networks are encoded at a genetic level rather than at the phenotype level of neural connections.
Today, in many clustering applications we deal with a large amount of data that are delivered in form of data streams. To be able to face the problem of analyzing the data as soon as they are produced, we need to build models that can be incrementally updated. This paper presents an adaptation of a bio-inspired algorithm that dynamically creates and visualizes groups of data, to data stream clustering. We introduce a merge operator that can summarize a group of data and a split operator that uses information of a very small set of supervised data and permits to adapt the clustering to a change in the data stream.
Geometric particle swarm optimization (GPSO) is a recently introduced formal generalization of a simplified form of traditional particle swarm optimization (PSO) without the inertia term that applies naturally to both continuous and combinatorial spaces. In this paper, we propose an extension of GPSO, the inertial GPSO (IGPSO), that generalizes the traditional PSO endowed with the full equation of motion of particles to generic search spaces. We then formally derive the specific IGPSO for the Hamming space associated with binary strings and present experimental results for this new algorithm.
We analyze the influence of quantization noise in fitness values on the search performance of Particle Swarm Optimization (PSO) and propose methods for reducing the negative influence of the noise to help realize a practical Interactive PSO. First, we compare the convergences of PSO and genetic algorithms (GA) with several different levels of quantized fitness values and show that PSO has a higher sensitivity to quantization noise than GA. Second, we analyze the sensitivity of each of the three components that determine the subsequent generation's PSO velocities and show that the sensitivities of the three components are almost equivalent. This implies that we need to develop methods for reducing the effect of quantization noise on all three components of the PSO velocity. As one of the solution, we propose a method using the average location of multiple global bests of same fitness value and another method for multimodal searching spaces using sub-global bests obtained by clustering.
We describe a physico-chemical model relating measured fluorescence intensities on oligonucleotide microarrays to the underlying specific target concentration in the hybridised solution via a hyperbolic isotherm response function. The model includes various chemical reactions occurring at the microarray surface and in bulk solution during hybridisation, including specific and non-specific hybridisation, and also the effects of probe-target dissociation during the post hybridisation washing phase. We analyse the distribution of fluorescence intensities for a complete microarray in the light of this physico-chemical model. Our results indicate that the majority of signals in a typical microarray experiment, though not those of the highly expressed genes, belong to the low concentration, linear part of the isotherm. Nevertheless, recognising the existence of the asymptotic saturation part of the isotherm is important for interpreting this distribution over the entire intensity range.
Uncertainties are commonly present in optimization systems, and when they are considered in the design stage, the problem usually is called a robust optimization problem. Robust optimization problems can be treated as noisy optimization problems, as worst case minimization problems, or by considering the mean and standard deviation values of the objective and constraint functions. The worst case scenario is preferred when the effects of the uncertainties on the nominal solution are critical to the application under consideration. Based on this worst case scenario, we developed the [I]RMOEA (Interval Robust Multi-Objective Evolutionary Algorithm), a hybrid method that combines interval analysis techniques to deal with the uncertainties in a deterministic way and a multiobjective evolutionary algorithm. We introduce [I]RMOEA and illustrate it on three robust test functions based on the ZDT problems. The results show that [I]RMOEA is an adequate way of tackling robust optimization problems with evolutionary techniques taking advantage of the interval analysis framework.
Previous study shows that using a random immigrant scheme in a cooperative coevolutionary algorithm (RI-CCEA) can significantly track the moving peaks in dynamic optimization. In this paper, we further investigate its behavior in the multi-modal environments where peak locations, peak coverage and peak heights of the moving peaks are changing during the course of optimization. Of the particular interest to us is the different combinations of the collaboration methods used by the original individuals and the RI individuals of the CCEA populations. Empirical comparisons show that in the moderate-changing or slow-changing environments, using the best collaborations in original individuals in the RI-CCEA outperforms other variants in our experiments, while the choice of the collaboration methods in RI individuals is insignificant. In a fast-changing environment, using the random collaborations in original individuals is crucial to achieve a better performance and the choice of the collaboration methods in RI individuals is also significant.
Cellular automata represent a computational model that is based on updating the states of the cells, that are arranged in a regular structure, by means of local interactions between the cells. Cellular automata have often been utilized as a developmental model in engineering areas to solve many complex problems. In the area of the evolutionary algorithms, cellular automata can be applied as an indirect mapping between genotypes and phenotypes. In the recent years, this approach has successfully been applied on the evolutionary development of digital circuits at the gate level. Combinational multipliers represent a class of circuits that is usually considered as hard task for the design using the evolutionary techniques. In our previous research regarding the cellular automata-based development, 2x2-bit multipliers were successfully evolved using this approach. Combinational multipliers have been chosen in this paper to demonstrate capabilities of an advanced developmental system that allows to apply cellular automata of different sizes in order to design larger instances of this kind of circuits. In the experiments presented herein, the 2x3-bit and 3x3-bit multipliers will be considered which represent the first case when such instances of multipliers have been successfully developed at the gate level using cellular automata. The proposed developmental model is investigated in detail with respect to the success rate of the evolutionary experiments for different experimental setups (such as the cellular automata size, the number of cell states and developmental steps). Moreover, it will be demonstrated that different ways of connections of the circuit outputs can be utilized without a significant influence on the successfulness of the evolutionary process.
Artificial development has been introduced by many as a means to simplify the genome of the evolutionary process and thus aid scalability of evolutionary techniques. However, this simplicity in the genome comes at the cost of complexity in the mapping. This is perhaps not so suprising when we look to biology and the complicated process of gene regulation. However, creating an artificial representation of this complicated process is far from straight forward. To simplify such a process, we need to acquire knowledge and define some form of rules to guide the creation of development models. The work presented herein investigates an existing development model, identifying which factors in the model are part of the regulatory decisions. Further, experimental work looks more closely at protein pre-conditions within the model. The results form the basis for more generalised preliminary rules for protein pre-conditions creation.
In this paper we propose a new diversity measure based on the correlation of bit strings for the analysis of Genetic Programming (GP) experiments. The diversity measure has been applied to analyse the impact of pruning on the diversity of a population during genetic programming and it's relation to the convergence time of the fitness function. To show the usability of the proposed diversity measure a GP experiment is introduced where simulated Jasmine robots have to learn a collison avoidance behaviour to find their way through a maze. A full analysis of this experiment is given with different fixed pruning strategies in respect to the population diversity and fitness. The GP has been done on behaviour-based robot controllers implemented in MDL2e. MDL2e has the advantage that it provides a very compact bit string representation of the control programme, which can be used for diversity analysis.
As the research of dynamic optimization arising, memory-based strategy has gained public attention recently. However, few studies on developing dynamic multi-objective optimization algorithms and even fewer studies on multiobjective memory-based strategy were reported previously. In this paper, we try to address such an issue by proposing several memory-based multi-objective evolutionary algorithms and experimentally investigating different multi-objective dynamic optimization schemes, which include restart, explicit memory, localsearch memory and hybrid memory schemes. This study is to provide pre-trial research of how to appropriately organize and effectively reuse the changed Pareto-optimal decision values (i.e., Pareto-optimal solutions: POS) information.
In this paper we present an evolutionary method that can deal with the specific problem requirements of adaptivity, scalability and robustness. These requirements are increasingly observed in the areas of pervasive and autonomic computing, and the area of collective robotics. For the purpose of this paper, we concentrate on the problem domain of collective robotics, and more specifically on a surveillance task for such a collective. We present the Situated Evolution Method as a viable alternative for classical evolutionary methods specifically for problem domains with the aforementioned requirements. By means of simulation experiments for a surveillance task, we show that our new method does not lose performance in comparison with a classical evolutionary method, and it has the important design and deployment advantage of being adaptive, scalable and robust.
This paper presents a new unified design flow developed within the Perplexus project that aims at accelerating parallelizable data-intensive applications in the context of ubiquitous computing. This contribution relies on the JubiTool: a set of integrated tools (JubiSplitter, JubiCompiler, UbiAssembler), allowing respectively to extract, compile and assemble parallelizable parts of applications described in Jubi language. Jubi is a modified Java agent based extention (JADE) dedicated to the Ubichip (the bio-inspired chip developed within the confines of the Perplexus project). By appending hardware directives to a software agent description, the inherent flexibility of software is combined with the runtime performance of a hardware execution. In the case of typical Perplexus applications such as the Spiking Neural Network simulator, this contribution takes profit of the intrinsic property of the Ubichip in terms of parallelism resulting in an expected speedup of at least one order of magnitude. Finally, this hybrid (SW/HW) flow could be easily modified and adapted to support other kind of distributed platforms.
A new design method called MORDE (multi-objective robust design exploration), which conducts both a multi-objective robust optimization and data mining for analyzing trade-offs, is proposed. For the robust optimization, probabilistic representation of design parameters is incorporated into a multi-objective genetic algorithm. The means and standard deviations of responses of evaluation functions to uncertainties in design variables are evaluated by descriptive Latin hypercube sampling using Kriging surrogate models. To extract trade-off control rules further, a new approach, which combines the association rule with an 'aspiration vector,' is proposed. MORDE is then applied to an industrial design problem concerning a centrifugal fan. Taking dimensional uncertainty into account, MORDE then optimized the means and standard deviations of the resulting distributions of fan efficiency and turbulent noise level. The advantages of MORDE over traditional approaches are shown to be the diversity of the solutions and the quantitative controllability of the trade-off balance among multiple objective functions.
A combination of backpropagation and neuroevolution is used to train a neural network visual controller for agents in the Quake II environment. The agents must learn to shoot an enemy opponent in a semi-visually complex environment using only raw visual inputs. A comparison is made between using normal neuroevolution and using neuroevolution combined with backpropagation for Lamarckian adaptation. The supervised backpropagation imitates a hand-coded controller that uses non-visual inputs. Results show that using backpropagation in combination with neuroevolution trains the visual neural network controller much faster and more successfully.
It is advantageous for colony robots to be autonomous and self-sufficient. This requires them to perform their duties while maintaining enough energy to operate. Previously, we reported the equipping of power storage for legged robots with high capacitance capacitors, the configuration of one of these robots to effectively use its power storage in a colony recharging system, and the learning of a control program that enabled the robot to navigate to a charging station in simulation. In this work, we report the learning of a control program that allowed the simulated robot to perform area coverage in a self-sufficient framework that made available the best pre-learned navigation behavior module.
In this paper, the aerodynamic shape optimization problems with uncertain operating conditions has been addressed. After a review of robust control theory and the possible approaches to take into account uncertainties, the use of Taguchi robust design methods in order to overcome single point design problems in Aerodynamics is proposed. Under the Taguchi concept, a design with uncertainties is converted into an optimization problem with two objectives which are the mean performance and its variance, so that the solutions are as less sensitive to the uncertainty of the input parameters as possible. Furthermore, the Multi-Criterion Evolutionary Algorithms (MCEAs) are used to capture a set of compromised solutions (Pareto front) between these two objectives. The flow field is analyzed by Navier-Stokes computation using an unstructured mesh. The proposed approach drives to the solution of a multi-objective optimization problem that is solved using a modification of a Non-dominated Sorting Genetic Algorithm (NSGA). In order to reduce the number of expensive evaluations of the fitness function a Response Surface Modeling (RSM) is employed to estimate the fitness value using the polynomial approximation model. During the solution of the optimization problem a Semi-torsional Spring Analogy is used for the adaption of the computational mesh to all the obtained geometrical configurations. The proposed approach is applied to the robust optimization of the 2D high lift devices of a business aircraft by maximizing the mean and minimizing the variance of the lift coefficients with uncertain free-stream angle of attack at landing and takeoff flight conditions, respectively.
Particle Swarm Optimisation (PSO) is increasingly being applied to optimisation of problems in engineering design and scientific investigation. While readily adapted to single-objective problems, its use on multi-objective problems is hampered by the difficulty of finding effective means of guiding the swarm in the presence of multiple, competing objectives. This paper suggests a novel approach to this problem, based on an extension of the concepts of spatial social networks using a model of the behaviour of locusts and crickets. Comparison is made between neighbouring particles based on Pareto dominance, and a corresponding repulsion between particles added to previously suggested attractive forces. Computational experiments demonstrate that the new, spatial, social network optimisation algorithm can provide results comparable to a conventional MOPSO algorithm, and improved coverage of the Pareto-front.
Evolutionary multi-objective optimization algorithms are commonly used to obtain a set of non-dominated solutions for over a decade. Recently, a lot of emphasis have been laid on hybridizing evolutionary algorithms with MCDM and mathematical programming algorithms to yield a computationally efficient and convergent procedure. In this paper, we test an augmented local search based EMO procedure rigorously on a test suite of constrained and unconstrained multi-objective optimization problems. The success of our approach on most of the test problems not only provides confidence but also stresses the importance of hybrid evolutionary algorithms in solving multi-objective optimization problems.
Conformational sampling, the computational prediction of the experimental geometries of small proteins (folding) or of protein-ligand complexes (docking), is often cited as one of the most challenging multimodal optimization problems. Due to the extreme ruggedness of the energy landscape as a function of geometry, sampling heuristics must rely on an appropriate trade-off between global and local searching efforts. A previously reported 'planetary strategy', a generalization of the classical island model used to deploy a hybrid genetic algorithm on computer grids, has shown a good ability to quickly discover low-energy geometries of small proteins and sugars, and sometimes even pinpoint their native structures - although not reproducibly. The procedure focused on broad exploration and used a tabu strategy to avoid revisiting the neighborhood of known solutions, at the risk of 'burying' important minima in overhastily set tabu areas. The strategy reported here, termed 'divide-and-conquer planetary model' couples this global search procedure to a local search tool. Grid nodes are now shared between global and local exploration tasks. The phase space is cut into 'cells' corresponding to a specified sampling width for each of the N degrees of freedom. Global search locates cells containing low-energy geometries. Local searches pinpoint even deeper minima within a cell. Sampling width controls the important trade-off between the number of cells and the local search effort needed to reproducibly sample each cell. The probability to submit a cell to local search depends on the energy of the most stable geometry found within. Local searches are allotted limited resources and are not expected to converge. However, as long as they manage to discover some deeper local minima, the explored cell remains eligible for further local search, now relying on the improved energy level to enhance chances to be picked again. This competition prevents the system to waste too much effort in fruitless local searches. Eventually, after a limited number of local searches, a cell will be 'closed' and used - first as 'seed', later as tabu zone - to bias future global searches. Technical details and some folding and docking results will be discussed
Locust Swarms are a new multi-optima search technique explicitly designed for non-globally convex search spaces. They use 'smart' start points to scout for promising new areas of the search space before using particle swarms and a greedy local search technique (e.g. gradient descent) to find a local optimum. These scouts start a minimum distance away from the previous optimum, and this gap is an important part of achieving a non-convergent search trajectory. Equally, the search for 'smart' start points centers around the previous local optimum, and this provides the basis for also having a non-random search trajectory. Experiments on a 30-dimensional rotated Schwefel function demonstrate that the ability of Locust Swarms to successfully balance these two search characteristics is an important factor in its ability to effectively explore this non-globally convex search space.
In this work we put forward a comprehensive study on the design of global stopping criteria for multi--objective optimization. We propose a global stopping criterion, denominated MGBM criterion, that combines the mutual domination rate (MDR) improvement indicator with a simplified Kalman filter that is used for evidence gathering process. The MDR indicator, which is introduced along, is a special purpose solution meant for the stopping task. It is capable of gauging the progress of the optimization with a low computational cost and therefore suitable for solving complex or many--objective problems. The viability of the proposal is established by comparing it with some other possible alternatives. It should be noted that, although the criteria discussed here are meant for MOPs and MOEAs, they could be easily adapted to other softcomputing or numerical methods by substituting the local improvement metric with a suitable one.
This paper analyzes the numerical optimization problems from the viewpoint of multiagent systems. First, Macro-Agent Evolutionary Model (MacroAEM) is proposed with the intrinsic properties of decomposable functions in mind. In this model, a subfunction forms a macro-agent, and 3 new behaviors, namely competition, cooperation, and selfishness, are developed for macro-agents to optimizing objective functions. Second, MacroAEM model is integrated with multiagent genetic algorithm, which results a new algorithm, Hierarchical MultiAgent Genetic Algorithm (HMAGA). The convergence of HMAGA is analyzed theoretically and the results show that HMAGA converges to the global optima. In experiments, HMAGA is applied to a kind of complicated decomposable function, namely Rosenbrock function. The results show that HMAGA achieves a good performance, especially for the high-dimensional functions. In addition, the analyses on time complexity demonstrate that HMAGA has a good scalability.
A general framework for the reconfiguration of satellite constellations is developed for the operational scenario when a loss of capacity has occurred and the future configuration must be constructed from the remaining assets. A multi-objective evolutionary algorithm, ε-NSGA-2, adapted for use on large heterogeneous clusters, facilitated the exploration of a six-dimensional fitness landscape for several loss scenarios involving the Global Positioning System Constellation. An a posteriori decision support process was used to characterize and evaluate non-traditional but innovative constellation designs identified. The framework has enhanced design discovery and innovation for extremely complex space domain problems that have traditionally been considered computationally intractable.
Recent work has shown that it is possible to evolve heuristics for solving propositional satisfiability (SAT) problems which are competitive with the best hand-coded heuristics. However, previous work was limited by the computational resources required in order to evolve successful heuristics. In this paper, we describe a massively parallel genetic programming system for evolving SAT heuristics. Runs using up to 5.5 CPU core years of computation were executed, and resulted in new SAT heuristics which significantly outperform hand-coded heuristics.
Dynamic multi-objective optimization (DMO) is a challenging class of problems where the objective and/or the constraint function(s) change over time. DMO has received little attention in the past and none of the existing multi-objective optimization algorithms have performed too well on the set DMO test problems. In this paper, we introduce a memetic algorithm (MA) embedded with a sequential quadratic programming (SQP) solver for faster convergence and an orthogonal epsilon-constrained formulation is used to deal with multiple objectives. The performance of the memetic algorithm is compared with an evolutionary algorithm (EA) embedded with a Sub-EA with and without restart mechanisms on two benchmark functions FDA1 and modified FDA2. The memetic algorithm consistently outperforms the evolutionary algorithm for both FDA1 and modified FDA2 problems.
Memetic algorithms (MAs) arise as very effective algorithms to obtain reliable and high accurate solutions for complex continuous optimization problems. Nowadays, high dimensional optimization problems are an interesting field of research. Its high dimension introduces new problems for the optimization process, making recommendable to test the behavior of the optimization algorithms to large-scale problems. Also, with a higher dimensionality the neighborhood is also increased. Thus, the local search algorithms must be applied with a higher intensity, in particular to most promising solutions. Considering these problems, we propose a memetic algorithm that adapt its local search parameters for each individual in function on its features. Our memetic algorithm approach assigns to each individual a local search intensity that depends on its features, by chaining different local search applications. With this technique of search chains, at each stage the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. We make experiments of our proposal using the benchmark problems defined in the Special Session or Competition on Large Scale Global Optimisation, on the IEEE Congress on Evolutionary Computation in 2008 (CEC'2008) (Dimension 100, 500 and 1000). First, we test different LS methods to identify the best one for this type of problem. Then, we compare the AM proposed with the algorithms used into the CEC'2008 competition, obtaining that our proposal is a very promising algorithm for this type of high-dimensional problems: with dimension 500 our proposal is the second best of the compared algorithms, and the best memetic algorithm. Thus, the proposal is a very promising algorithm for large scale optimization problems, and it could be improved more in the future.
Interested in Evolutionary Robotics, this paper focuses on the acquisition and exploitation of memory skills. The targeted task is a well-studied benchmark problem, the Tolman maze, requiring in principle the robotic controller to feature some (limited) counting abilities. An elaborate experimental setting is used to enforce the controller generality and prevent opportunistic evolution from mimicking deliberative skills through smart reactive heuristics. The paper compares the prominent NEAT approach, achieving the non-parametric optimization of Neural Nets, with the evolutionary optimization of Echo State Networks, pertaining to the recent field of Reservoir Computing. While both search spaces offer a sufficient expressivity and enable the modelling of complex dynamic systems, the latter one is amenable to robust parametric, linear optimization with Covariance Matrix Adaptation-Evolution Strategies.
Very recently bacterial foraging has emerged as a powerful technique for solving optimization problems. In this paper, we attempt to implement a micro-bacterial foraging optimization algorithm, which evolves with a very small population compared to its classical version. In this modified bacterial foraging algorithm, the best bacterium is kept unaltered, whereas the other population members are reinitialized. This new small population μ-BFOA is tested over a number of numerical benchmark problems for high dimensions and we find this to outperform the normal bacterial foraging with a larger population as well as with a smaller population.
For the past two decades simulated annealing has been playing a crucial role in the design of optimization strategies for flow shop scheduling applications. This paper presents an efficient simulated annealing algorithm for minimizing the total flow time in permutation flow shop scheduling problems. Empirical results demonstrate the improvement in solution quality obtained by the proposed approach over state-of-the-art methods in the literature.
Paper describes method for finding transmitter parameters (location and power) for optimal electromagnetic radiation distribution in observed area. Constrains are protected areas inside observed area where strength of electric field is limited because of permanent people presence. In observed area one wish to obtain strength of electric field which is higher than lower limit value to cover the area with enough reception signal strength. On the other side electric field inside protected areas has to be lower than prescribed upper limit. Those two conditions are contradictory. In here described investigation genetic algorithm is used to find transmitter parameters (location and power) constrained by above mentioned conditions. Main purpose of investigations is examining applicability of procedure. Initial investigation is limited to rectangular planar observing area with one transmitter and with different formation and size of protected areas (areas in which strength of electric field is limited because of permanent people presence). Procedure has been repeated and results statistically analyzed. Based on those results it can be concluded that procedure is applicable and it is justified to continue investigations for more complex and more realistic situations e.g. more transmitters with directed radiations and for three dimensional spaces.
This paper describes the use of a new evolutionary method named Genetic Relation Algorithm (GRA) for reducing the number of class association rules extracted by other methods such as Apriori, Genetic Network Programming(GNP) , etc. The purpose is to generate a small number of class association rules in order to delete irrelevant and redundant rules. A reduced rule set has advantages as it provides only useful rules and makes its analysis more efficient. Our approach is based on evaluating the distances between rules for evolving GRA and also evaluating the distances between the data in the test set and the rules for classification. Two matching criteria are presented: complete match and partial match. The classification accuracy obtained by our method is better compared to other reported results in multi-class datasets showing an impressive reduction rate.
The mining of meaningful shapes of time series is done widely in order to find shapes that can be used, for example, in classification problems or in summarizing signals. Normally, shapes that summarize periodic signals have to be mined visually, and in order to find a shape of high quality, several tests haves to be made. This makes visual mining slow and sometimes even frustrating. A method for summarizing a periodic time series automatically is presented in this study. The method is based on evolutionary computation and the results show that by using it, shapes can be found that summarize a time series better than shapes found using visual mining.
Differential evolution (DE) is a powerful yet simple evolutionary algorithm for optimizing real valued optimization problems. Traditional investigations with differential evolution have used a single mutation operator. Using a variety of mutation operators that can be integrated during evolution could hold the potential to generate a better solution with less computational effort. In view of this, in this paper a mixed mutation strategy which uses the concept of evolutionary game theory is proposed to integrate basic differential evolution mutation and quadratic interpolation to generate a new solution. Throughout of this paper we refer this new algorithm as, differential evolution with mixed mutation strategy (MSDE). The performance of proposed algorithm is investigated and compared with basic differential evolution. The experiments conducted shows that proposed algorithm outperform the basic DE algorithm in all the benchmark problems.
This paper explores a process-oriented approach to complex systems design, using massive fine-grained concurrency, mobile channels and mobile processes. The complex systems studied are self-organising, with emergent and evolving behaviours (apparent at the global level) arising from massive interactions between relatively simple components (that have only local knowledge). Classical ant foraging is used as a case study. Processes are used to represent space, environmental factors and the ants themselves. Ant processes (like all processes) only have knowledge of their internal state (looking for food, looking for their nest) and what they can glean from their local neighbourhood (by interacting with the processes making up that neighbourhood). The networks constructed are dynamic, changing as the ants move around and environmental factors are introduced and modified. The paper reports on two mechanisms for achieving this: channel mobility and process mobility. The language for implementation is occam-pi, which has the necessary concurrency mechanisms built in as fundamental primitives and whose semantics are rooted in the process algebras of CSP and the pi-calculus. Performance figures are given, including speedup curves for multicores, and some conclusions drawn.
In a real-world, labor market consist of employer and employee, and these individuals form relationship through mutual interactions. This paper mainly focuses on development of multi-agent based evolutionary labor market by using co-evolutionary computation and game theory. Co-evolutionary computation is used to define strategy of each agent dynamically, and game theory is used for modeling relationship between employee and employer. Gift exchange game is selected as game model regard to feature of proposed labor market framework. Various experiments were performed, and we analyzed the variation of interactions between employee and employer. Through the experimental result, we concluded that balanced power between employee and employer is important factor in maintenance and extension of labor market.
Visceral leishmaniasis is a parasitic disease that is usually fatal if untreated. Host resistance is thought to involve the accumulation of inflammatory cells into structures called granulomas. To date, the possible processes underlying granuloma formation are not fully understood. The importance of modelling in immunology is increasing particularly for dynamic processes that are hard to study in vivo over extended periods of time. Appropriate modelling can provide novel insights that might help deepen the understanding of phenomena and/or help guide experimental work. This paper discusses initial studies on the regulation of granuloma using a combination of UML like modelling and agent based simulation.
The dynamic of complex social networks is nowadays one of the research areas of growing importance. The knowledge about the temporal changes of the network topology and characteristics is crucial in networked communication systems in which accurate predictions are important. In this paper a physics-inspired method to track the changes within complex social network is proposed. This method is based on the dynamic molecular modelling technique used in physics for simulation of large sets of interacting particles. The data for the conducted research was derived from e-mail communication within big company (Wroclaw University of Technology). From this information the social network of employees was extracted. The created social network was utilized to evaluate the methodology of social network dynamics modelling proposed by authors.
Elevator group control systems are the transportation systems for handling passengers in the buildings. With the increasing demand for high-rise buildings, Multi-Car Elevator System(MCES) where two cars operate separately and independently in an elevator shaft are attracting attention as the next novel elevator system. Genetic Network Programming(GNP), one of the evolutionary computations, can realize a rule based MCES due to its directed graph structure of the individual, which makes the system more flexible. This paper discusses MCES using GNP for the buildings with 30 floors. The performance of MCES are examined and compared with Double-Deck Elevator System(DDES).
This paper presents recently introduced learning algorithm called Extreme Learning Machine (ELM) for Single-hidden Layer Feed-forward Neural-networks (SLFNs) which randomly chooses hidden nodes and analytically determines the output weights of SLFNs. ELM avoids problems like local minima, improper learning rate and over fitting commonly faced by iterative learning methods and completes the training very fast. We have evaluated the multi-category classification performance of ELM on five different datasets related to bioinformatics namely, the Breast Cancer Wisconsin data set, the Pima data set, the Heart-Statlog data set, the Hepatitis data set and the Hypothyroid data set. A detailed analysis of different activation functions with varying number of neurons is also carried out which concludes that algebraic sigmoid function outperforms all other activation functions on these datasets. The evaluation results indicate that ELM produces better classification accuracy with reduced training time and implementation complexity compared to earlier implemented models.
This paper proposes an algorithm using Multi-objective Particle Swarm Optimization (MOPSO) for finding robust solutions against small perturbations of design variables. If an optimal solution is sensitive to small perturbations of variables, it may be inappropriate or risky for practical use. Robust optimization finds solutions which are moderately good in terms of optimality and also good in terms of robustness against small perturbations of variables. The proposed algorithm formulates robust optimization as a bi-objective optimization problem, and finds robust solutions by searching for Pareto solutions of the bi-objective problem. This paper also proposes a hybridization of MOPSO and quasi-Newton method as an attempt to design effective memetic algorithm for robust optimization. Experimental results have shown that the proposed algorithms could find robust solutions effectively. The effect and drawback of the hybridization were also clarified by the experiments, helping design an effective memetic algorithm for robust optimization.
Most optimization algorithms that use probabilistic models focus on extracting the information from good solutions found in the population. A selection method discards the below-average solutions. They do not contribute any information to be used to update the models. This work proposes a new algorithm, Combinatorial Optimization with Coincidence (COIN) that makes use of both good and not-good solutions. A Generator represents a probabilistic model of the required solution, is used to sample candidate solutions. Reward and punishment schemes are incorporated in updating the generator. The updating values are defined by selecting the good and not-good solutions. It has been observed that the not-good solutions contribute to avoid producing the bad solutions. The multi-objective version of COIN is also introduced. Several benchmarks of multi-objective problems of real world industrial applications are reported.
This paper concerns a non-traditional evolutionary robotics approach to robot navigation. Navigation is presented as a problem of two conflicting objectives. The first concerns a classical 'amalgamated' objective, which has been traditionally used to increase speed, move straight as possible, and at the same time avoid obstacles. The second objective is devised to simultaneously encourage a sequential acquisition of targets. To solve the presented problem a modification of the well known NSGA-II algorithm has been performed. The proposed approach is tested using a simulation of a Khepera. The study sheds light on different aspects of the aforementioned problem and on the applicability of evolutionary multi-objective optimization to the simultaneous learning of a variety of controllers for deferent behaviors. Finally, based on this initial study, future work is suggested, which may allow to shift such multi-objective evolutionary studies from toy problems to more realistic situations.
In this paper, a multi-objective evolutionary algorithm based on adaptive discrete Differential Evolution is proposed for multi-objective optimization problems, especially in discrete domain. By introducing Differential Evolution to multi-objective optimization field, a novel adaptive discrete Differential Evolution strategy is presented firstly to enhance the ability of global exploration, so that the proposed multi-objective evolutionary algorithm can achieve the better approximate Pareto-optimal solutions. Furthermore, the proposed multi-objective evolutionary algorithm integrates the adaptive discrete Differential Evolution strategy with a fast Pareto ranking strategy and a truncating operation based on crowding density and Pareto rank to maintain the good diversity of evolutionary population. The simulations are conducted for a set of standard Multi-objective 0/1 knapsack problems which are the typical NP-hard problems. The performance of the proposed multi-objective evolutionary algorithm is compared with that of SPEA and NSGA-II which are state-of-the-art. Experimental results indicate that the proposed multi-objective evolutionary algorithm is more effective and efficient.
In this paper, Multi-objective evolutionary programming (MOEP) using rank-sum sorting with diversified selection is introduced. The performance of this algorithm as well as MOEP with non-domination sorting on the set of benchmark functions provided for CEC2009 Special Session and competition on Multi-objective Optimization are reported. With this rank-sum sorting and diversified selection, the speed of the algorithm has increased significantly, in particular by about twenty times on five objective problems when compared with the implementation using the non-domination sorting. Beside this, the proposed approach has performed either comparable or better than the MOEP with non-domination sorting.
In this paper, we propose Multiobjective Self-adaptive Differential Evolution algorithm with objective-wise learning strategies (OW-MOSaDE) to solve numerical optimization problems with multiple conflicting objectives. The proposed approach learns suitable crossover parameter values and mutation strategies for each objective separately in a multi-objective optimization problem. The performance of the proposed OW-MOSaDE algorithm is evaluated on a suit of 13 benchmark problems provided for the CEC2009 MOEA Special Session and Competition (http://www3.ntu.edu.sg/home/epnsugan/) on Performance Assessment of Constrained / Bound Constrained Multi-Objective Optimization Algorithms.
An essential behaviour of biological neural networks is the switching between different dynamical stages i.e. during development, learning, attention or memory formation. This seems to be a key element the understanding of the balance of stability and flexibility of biological information systems and should also be implemented in biologic plausible artificial neural networks. The parameter estimation of such artificial networks to fit it to the biological behavior in the different stages is a multi-objective problem. We show a multi-population genetic algorithm to get useful parameter combinations with an adapted cross population estimation of fitness and recombination of genes. The algorithm is tested on parameter fitting of a working memory model and further application of dopamine modulated learning is discussed.
JADE is a recent variant of Differential Evolution (DE) for numerical optimization, which has been reported to obtain some promising results in experimental study. However, we observed that the reliability, which is an important characteristic of stochastic algorithms, of JADE still needs to be improved. In this paper we apply two strategies together on the original JADE, to dedicatedly improve the reliability of it. We denote the new algorithm as rJADE. In rJADE, we first modify the control parameter adaptation strategy of JADE by adding a weighting strategy. Then, a "restart with knowledge transfer" strategy is applied by utilizing the knowledge obtained from previous failures to guide the subsequent search. Experimental studies show that the proposed rJADE achieved significant improvements on a set of widely used benchmark functions.
Migration policies in distributed evolutionary algorithms are bound to have, as much as any other evolutionary operator, an impact on the overall performance. However, they have not been an active area of research until recently, and this research has concentrated on the migration rate. In this paper we compare different migration policies, including our proposed 'multikulti' methods, which choose the individuals that are going to be sent to other nodes based on the principle of 'multiculturalism': the individual sent should be as different as possible to the receiving population (represented in several possible ways). We have checked this policy on two discrete optimization problems for different number of nodes, and found that, in average or in median, multikulti policies outperform others like sending the best or a random individual; however, their advantage changes with the number of nodes involved and the difficulty of the problem. The success of this kind of policies will be explained via the measurement of entropies, which are known to have an impact in the performance of the evolutionary algorithm.
In multiobjective optimization there is often the problem of the existence of a large number of objectives. For more than two objectives there is a difficulty with the representation and visualization of the solutions in the objective space. Therefore, it is not clear for the decision maker the trade-off between the different alternative solutions. Thus, this creates enormous difficulties when choosing a solution from the Pareto-optimal set and constitutes a central question in the process of decision making. Based on a statistical method, Principal Component Analysis, the problem of reduction of the number of objectives is addressed. Several test examples with different number of objectives have been studied in order to evaluate the process of decision making through these methods. Preliminary results indicate that this statistical approach can be a valuable tool on decision making in multiobjective optimization.
This paper proposes a multiobjective quantum-inspired evolutionary algorithm (MQEA) to design efficient fuzzy path planner of mobil robot. MQEA employs the probabilistic mechanism inspired by the concept and principles of quantum computing. As the probabilistic individuals are updated by referring to nondominated solutions in the archive, population converges to Pareto-optimal solution set. In order to evaluate the performance of proposed MQEA, robot soccer system is utilized as a mobile robot system. Three objectives such as elapsed time, heading direction and posture angle errors are designed to obtain robust fuzzy path planner in the robot soccer system. Simulation results show the effectiveness of the proposed MQEA from the viewpoint of the proximity to the Pareto-optimal set. Moreover, various trajectories by the obtained solutions from the proposed MQEA are shown to verify the performance and to see its applicability.
In this paper we discuss a real-life problem in rail crew rostering. Specific emphasis is placed on the requirements of advanced approaches in rostering and the usage of optimization-based decision support. The modeling of the rostering problems is discussed including the treatment of constraints, the consideration of preferences, and the formulation of several objective functions. The specific solving method of the problem using an evolutionary algorithm and visualization and navigation tools for decision support are sketched briefly and some preliminary results are shown. Finally, some conclusions are presented.
This paper proposes a multiobjective dispatch model to operate hydroelectric power plants. The model is composed of two algorithms that are based on Genetic Algorithms. The first algorithm is used for the static dispatch of generating units and is aimed at maximizing plant efficiency on an hourly basis. The second step is a multiobjective technique for the daily operation of generating units. The two objectives are to maximize the plant efficiency and to minimize the number of startups and shutdowns of generating units. Data from a Brazilian power plant were used in the simulation of a daily operation. A daily load curve contains 24 static problems, each one solved on average in approximately 2 minutes. The second step was executed in approximately 99 seconds. The proposed model proved suitable for the daily operation of the hydroelectric power plant studied, given the low computational time, satisfactory efficiency and low number of generating units startups and shutdowns (only 12).
Many real-world optimization problems involve multiple conflicting objectives. Therefore, multi-objective optimization has attracted much attention of researchers and many algorithms have been developed for solving multi-objective optimization problems in the last decade. In this paper the multiple trajectory search (MTS) is presented and successfully applied to thirteen unconstrained and ten constrained multi-objective optimization problems. These problems constitute a test suite provided for competition in the Special Session & Competition on Performance Assessment of Constrained/Bound Constrained Multi-Objective Optimization Algorithms in CEC 2009. In the multiple trajectory search, a set of uniformly distributed solutions is first generated. These solutions will be separated into foreground solutions and background solutions. The search is focus mainly on foreground solutions and partly on background solutions. The MTS chooses and applies one of the three local search methods on solutions iteratively. The three local search methods begin their search in a very large "neighborhood". Then the neighborhood contracts step by step until it reaches a pre-defined tiny size, after then, it is reset to its original size. By utilizing such size-varied neighborhood searches, the MTS effectively solves the multi-objective optimization problems.
This article presents a new approach for automatically determining the optimal quantity and connectivity of the hidden-layer of a three-layer Feed-Forward Neural Network (FFNN) based on a theoretical and practical approach. The system (MINES) is a combination of Neural Network (NN), Back-Propagation (BP), Genetic Algorithm(GA), Mutual Information (MI), and clustering. BP is used to reduce the training-error while MI aides BP to follow an effective path. A GA changes the incoming synaptic connections of the hidden-nodes based on MI fitness. Assigning MI as the fitness of individuals brings a competition between hidden-nodes to acquire a higher amount of information from the error-space. Weight clustering is applied to reduce those hidden-nodes having similar weights. Experimental results are presented, and future directions discussed.
In human genetics, new technological methods allow researchers to collect a wealth of information about genetic variation among individuals quickly and relatively inexpensively. Studies examining more than one half of a million points of genetic variation are the new standard. Quickly analyzing these data to discover single gene effects is both feasible and often done. Unfortunately as our understanding of common human disease grows, we now believe it is likely that an individual's risk of these common diseases is not determined by simple single gene effects. Instead it seems likely that risk will be determined by nonlinear gene-gene interactions, also known as epistasis. Unfortunately searching for these nonlinear effects requires either effective search strategies or exhaustive search. Previously we have employed both filter and nature-inspired probabilistic search wrapper approaches such as genetic programming (GP) and ant colony optimization (ACO) to this problem. We have discovered that for this problem, expert knowledge is critical if we are to discover these interactions. Here we theoretically analyze both an expert knowledge filter and a simple expert-knowledge-aware wrapper. We show that under certain assumptions, the filter strategy leads to the highest power. Finally we discuss the implications of this work for this type of problem, and discuss how probabilistic search strategies which outperform a filtering approach may be designed.
Time series data abound and analysis of such data is challenging and potentially rewarding. One example is financial time series analysis. Most of the intelligent data analysis methods can be applied in principle, but evolutionary computing is becoming increasingly popular and powerful. In this paper we focus on one task of financial time series analysis – stock price forecasting based on historical data. The premise of this task is that the current price of a stock is dependent on the price of the same stock in the past. Here we consider an additional assumption, i.e., time dependency relevance, that the price in the nearer past is more relevant to the current price than that in the more distant past. This assumption appears intuitively sound, but needs formally validated. In this paper we set to test this assumption by introducing time weighting into similarity measures, as similarity is one of the key notions in time series analysis methods including evolutionary computing. We consider the generic neighbourhood counting similarity as it can be specialised for various forms of data by defining the notion of neighbourhood in a way that satisfies different requirements. We do so with a view to capturing time weights in time series. This results in a novel time weighted similarity for time series. A formula is also discovered for the similarity so that it can be computed efficiently. Experiments show that this similarity outperforms the standard Euclidean distance and a time weighted variant of it. We conclude that the time dependency relevance assumption is sound.
This paper is a preliminary study into the types of collective behavior tasks that are best solved by neuro-evolution approaches that evolve complete controllers versus those that evolve neurons. This research tests a hypothesis that for a multi-rover task, the best approach (for deriving effective collective behaviors) is to evolve complete Artificial Neural Network (ANN) controllers, and then combine controller behaviors as a complete collective behavior. Such methods are called Conventional Neuro- Evolution (CNE). This is opposed to methods such as Enforced Sub-Populations (ESP) which evolves individual neurons and then combines them to form complete ANN controllers. CNE and ESP approaches to evolving collective behavior solutions are tested comparatively in the multi-rover task. The multi-rover task requires that teams of rovers (controllers) cooperate in order to detect features of interest in a virtual environment. Results indicate that a CNE approach derives rover teams with a higher task performance and genotype diversity, comparative to ESP.
The wide application of Binary segmentation for grayscale images could be found in computer vision and pattern recognition, especially for the purpose of object identification and recognition with industry and military images. This paper proposes a noise robust binary segmentation approach which incorporates Ant Colony System (ACS) with the modified Fuzzy C-Means (FCM) clustering algorithm. The ACS first survey the whole image, adding an additional pheromone dimension other than grayscale on each pixel. The modified FCM then deems every pixel a 2-dimensional vector and classifies all image pixels into two categories. Experiments have demonstrated better segmentation results and the advantage of robustness against noise using this method.
A novel evolutionary algorithm, Organizational Evolutionary Algorithm for SATisfiability problems (OEA_SAT), is proposed in this paper. OEA_SAT first divides a SAT problem into several sub-problems, and each organization is composed of a sub-problem. Thus, three new evolutionary operators, namely the self-learning operator, the annexing operator and the splitting operator are designed with the intrinsic properties of SAT problems in mind. Furthermore, all organizations are divided into two populations according to their fitness. One is called best-population, and the other is called non-best-population. The idea behind OEA_SAT is to solve the sub-problem first, and then synthesize the solution for the original problem by adjusting the variables which have conflicts. Since the dimensions of sub-problems are smaller and the sub-ones are easy to be solved compared with the original one, the computational cost is reduced in this way. In the experiments, 3700 benchmark SAT problems in SATLIB are used to test the performance of OEA_SAT. The number of variables of these problems is ranged from 20 to 250. Moreover, the performance of OEA_SAT is compared with those of two well-known algorithms, namely WalkSAT and RFEA2. All experimental results show that OEA_SAT has a higher success ratio and a lower computational cost. OEA_SAT can solve the problems with 250 variables and 1065 clauses by only 1.524 seconds and outperforms all the other algorithms.
Wireless Sensor Networks (WSNs) provide an effective means to perform data acquisition in remote areas. However, limitations exist that prohibit their widespread use. In this paper, an object tracking algorithm based on Artificial Immune Systems (AIS) is proposed. Based on the immune network theory of AIS, the activities of wireless sensor nodes are stimulated by target in-coming objects but suppressed by other wireless sensor nodes based on a dynamic changing environment. When a sensor node is being suppressed, the sensor node will go to a low-power state momentarily, otherwise, it will be actively estimating the location of the target objects. In doing so, the energy efficiency of the overall network will be optimized through the dynamic stimulation and suppression of sensor nodes that is mediated by the immunity-based algorithm. A number of experiments are conducted to verify the algorithm in terms of the degree of accuracy in target tracking and the energy efficiency of the entire sensor network.
Real working agents normally operate in dynamic changing environments. These changes could either affect the efficiency of the agents' performance or even damage the functionality of the agent. Robustness is the key requirement to solve this problem. Inspired by nature, this paper demonstrates two mechanisms that contribute to individual's robustness in changing environments: evolution and degeneracy. Through evolution in damaging environment, evolved agents have to cope with changes in the environment and acquire robustness. Through degeneracy, individuals can maintain their fitness even when some damaged parts are involved in system function.
In this paper, we describes the simultaneous perturbation particle swarm optimization which is a combination of the particle swarm optimization and the simultaneous perturbation optimization method. The method has global search capability of the particle swarm optimization and gradient information by the simultaneous perturbation effectively. Some modifications of the method are described. Comparison between these methods and the ordinary particle swarm optimization are shown through five test functions and learning problem of neural network.
Modularity is an omnipresent feature of biological neural networks. It is also a cornerstone of indirect genetic encodings and developmental evolutionary algorithms for neural networks. Modularity may give evolution the ability to reflect regularities in the environment in its solutions, thus making good solutions easier to find. Furthermore, it has been proposed that the density of highly fit solutions is higher in modular networks than in non-modular networks. In this paper we investigate how the degree of modularity in neural networks affects the search landscape for neuroevolution. We use multi-objective evolution to explicitly guide evolution towards modular and non-modular areas of network search space. We find that the fitness landscape is radically different in these different areas, but that network modularity is not accompanied by increased efficiency on a modular classification task. We therefore cannot find support for the popular assumption that modular networks are 'better' than non-modular networks.
This paper proposes a framework, that incorporates evolutionary computation and wargame simulation, to investigate the role of information networks in organizing efficient supply chains for military logistics. Under the proposed framework, evolutionary computation is used to evolve the information networks, which are subsequently evaluated by playing simulation wargames. Through a series of simulation studies, in which various supply scenarios have been simulated, we have found that information networks play a substantial role in efficient demand estimation. Depending on the level of information uncertainty, i.e. the hostile force strength distribution, different topological characteristics of the information networks, i.e. different information relationships between supply nodes, are favored. The objective of the paper is to discover the fundamental principles for information networks and their interaction with supply chains. These principles are significant for new and/or future military concepts such as network centric warfare. We believe that the proposal of the framework and the discovery of those emergent topological characteristics would significantly contribute to the organizing of efficient supply chains for military logistic operations.
The application of on-line learning techniques to modern computer games is a promising research direction. In fact, they can be used to improve the game experience and to achieve a true adaptive game AI. So far, several works proved that neuroevolution techniques can be successfully applied to modern computer games but they are usually restricted to off-line learning scenarios. In on-line learning problems the main challenge is to find a good trade-off between the exploration, i.e., the search for better solutions, and the exploitation of the best solution discovered so far. In this paper we propose an on-line neuroevolution approach to evolve non-player characters in The Open Car Racing Simulator (TORCS), a state-of-the-art open source car racing simulator. We tested our approach on two on-line learning problems: (i) on-line evolution of a fast controller from scratch and (ii) optimization of an existing controller for a new track. Our results show that on-line neuroevolution can effectively improve the performance achieved during the learning process.
Industry applications of multiobjective optimization problems mostly are characterized by the demand for high quality solutions on the one hand. On the other hand an optimization result is desired which at any rate meets the time constraints for the evolutionary multiobjective algorithms (EMOA). The handling of this trade-off is a frequently discussed issue in multiobjective evolutionary optimization. Recently an online convergence detection algorithm (OCD) for EMOA based on statistical testing has been introduced. OCD is independent from any knowledge of the true Pareto front of the optimization problem. It automatically stops at the EMOA generation in which either only a very small variation or a trend stagnation of a set of multiobjective performance indicators are detected for a predefined number of generations. In the course of the paper, OCD is applied to two aerodynamic test cases provided by a global player of the aircraft industry. It is shown that OCD performs extremely well on these problems in terms of saved function evaluations and EMOA performance after the OCD stop generation.
The Symbrion project stands at the crossroads of Artificial Life and Evolutionary Robotics: a swarm of real robots undergoes online evolution by exchanging information in a decentralized Evolutionary Robotics Scheme: the diffusion of each individual's genotype depends both on its ability to survive in an unknown environment as well as its ability to maximize mating opportunities during its lifetime, which suggests an implicit fitness. This paper presents early research and prospective ideas in the context of large-scale swarm robotics projects, focusing on the open-ended evolutionary approach in the Symbrion project. One key issue of this work is to perform on-board evolution in a spatially distributed population of robots. A real-world experiment is also described which yields important considerations regarding open-ended evolution with real autonomous robots.
A Genetic Algorithm (GA) is used in this paper for the optimal operation of the pipeline systems under transient conditions caused by valve closure. Simulation of pipeline system is carried out here by the Implicit Method of Characteristics, a method recently developed and introduced by the authors. This method uses an element-wise definition for all the devices that may be used in a pipeline system. The advantages of this method lie in its capability of considering any arbitrary combination of devices in a pipeline system. The transient simulator is linked to a GA optimizer, which is then used to optimize the operation of a pipeline system under valve closure. One example problem of valve closure is used to test the performance of the proposed model. In this example, the GA is used to obtain the minimum valve closure time such that the pipeline system with predefined characteristics can withstand the induced pressure surge. Two pre-specified closure rules of linear and sinusoidal type were used and their corresponding results are presented and compared. The results clearly emphasize on the applicability of the proposed optimization model to control the water hammer effects by properly managing the valve closure in a pipeline system.
Potentially hazardous asteroids can be deflected away from the Earth using a kinetic impactor spacecraft. An optimal control problem is solved to find the time history of thrust magnitude and direction to steer the low-thrust spacecraft from the Earth to the asteroid so that the impact maximizes the resulting miss distance. Because the solution space considered by the optimizer is large and the objective function is complicated, intuition is not sufficient to provide an adequate initial guess for the nonlinear programming problem solver used to optimize all aspects of the trajectory. A recently developed shape-based trajectory approximation method coupled with a genetic algorithm is used to provide this initial guess to the optimizer and make the problem tractable.
This paper examines a simulation of the Beer Distribution Game and a number of optimisation approaches to this game. This well known game was developed at MIT in the 1960s and has been widely used to educate graduate students and business managers on the dynamics of supply chains. This game offers a complex simulation environment involving multidimensional constrained parameters. In this research we have examined a traditional genetic algorithm approach to optimising this game, while also for the first time examining a particle swarm optimisation approach. Optimisation is used to determine the best ordering policies across an entire supply chain. This paper will present experimental results for four complex customer demand patterns. We will examine the efficacy of our optimisation approaches and analyse the implications of the results on the Beer Distribution Game. Our experimental results clearly demonstrate the advantages of both genetic algorithm and particle swarm approaches to this complex problem. We will outline a direct comparison of these results, and present a series of conclusions relating to the Beer Distribution Game.
Radio Frequency IDentification (RFID) technology is increasingly being used to uniquely identify objects. An important component of RFID systems is the design of the antenna - which usually takes the form of a compacted meander line. This task becomes an optimisation problem as different designs will have different efficiencies and resonant frequencies. In this paper, we explore the use of a multi-objective version of ant colony system. This constructive meta-heuristic, as shown, is highly suitable for this problem.
This paper describes an approach to optimise transistor dimensions within a standard cell library. The goal is to extract high-speed and low-power circuits which are more tolerant to the random fluctuations that will be prevalent in future technology nodes. Using statistically enhanced SPICE models based on 3D-atomistic simulations, a Genetic Algorithm optimises the device widths within a circuit using a multi-objective fitness function. The results show the impact of threshold voltage variation can be reduced by optimising transistor widths, and suggest a similar method could be extended to the optimisation of larger circuits.
Although low-thrust propulsion is an interesting option for scientific and reconnaissance missions to targets in planetary space, like the Moon, associated transfer strategies pose challenging requirements in terms of optimal control. The method of Evolutionary Neurocontrol (ENC), which has been applied very successfully to interplanetary low-thrust transfer problems, is now used for solving this type of steering problem. For exemplary validation two low-thrust transfers from an Earth-bound (geostationary transfer orbit) into an orbit around the Moon are optimized with respect to minimum flight time.
Genetic algorithms (GAs) have been argued to constitute a flexible search thereby enabling to solve difficult problems which classical optimization methodologies may find hard to solve. This paper is intended towards this direction and show a systematic application of a GA and its modification to solve a real-world optimization problem of sizing a solar thermal electricity plant. Despite the existence of only three variables, this problem exhibits a number of other common difficulties --- black-box nature of solution evaluation, massive multi-modality, wide and non-uniform range of variable values, and terribly rugged function landscape -- which prohibits a classical optimization method to find even a single acceptable solution. Both GA implementations perform well and a local analysis is performed to demonstrate the optimality of obtained solutions. This study considers both classical and genetic optimization on a fairly complex yet typical real-world optimization problems and demonstrates the usefulness and future of GAs in applied optimization activities in practice.
The creation of staff rosters for emergency shifts for doctors is a complex task. To construct good rosters, many restrictions (e.g. holydays and workload) have to be taken into account. These restrictions have been mathematically specified for a concrete case in order to solve the problem afterwards with a straightforward genetic algorithm. Thereby the main focus lays on two different mutation methods and the combination of them. The results of this procedure will be discussed in this work.
A new evolutionary-based algorithm is proposed to solve the robot manipulator optimal path generation problem. The following scenario is considered: given a learnt joint path describing a robot manipulator simple task in the Cartesian space, an optimal path is calculated when a different initial joint configuration is considered. The optimization problem is formulated as the minimization of both the end-effector pose error and the total joint displacement so as to ensure convergence towards the learnt path and a smooth joint motion. To solve the optimization problem an algorithm based on an evolutionary method called Differential Evolution (DE) is used. DE is a stochastic direct search optimization method based on the evolution of a candidate solution population in an iterative process of mutation, recombination, and selection. Since the algorithm does not require the use of the Jacobian matrix during the kinematic inversion, singularities problems are overcome. Results on the optimal path generation of a six degrees of freedom robot manipulator are also presented.
In the present paper some metrics for evaluating the performance of evolutionary algorithms are considered. The capabilities of two different optimisation approaches are compared on three test cases, represented by the optimisation of orbital transfer trajectories. The complexity of the problem of ranking stochastic algorithms by means of quantitative indices is analyzed by means of a large sample of runs, so as to derive statistical properties of the indices in order to evaluate their usefulness in understanding the actual algorithm capabilities and their possible intrinsic limitations in providing reliable information.
The bootstrap problem is often recognized as one of the main challenges of evolutionary robotics: if all individuals from the first randomly generated population perform equally poorly, the evolutionary process won't generate any interesting solution. To overcome this lack of fitness gradient, we propose to efficiently explore behaviors until the evolutionary process finds an individual with a non-minimal fitness. To that aim, we introduce an original diversity-preservation mechanism, called behavioral diversity, that relies on a distance between behaviors (instead of genotypes or phenotypes) and multi-objective evolutionary optimization. This approach has been successfully tested and compared to a recently published incremental evolution method (multi-subgoal evolution) on the evolution of a neuro-controller for a light-seeking mobile robot. Results obtained with these two approaches are qualitatively similar although the introduced one is less directed than multi-subgoal evolution.
Pareto optimality is a criteria of individual evaluation originally introduced in multi-objective evolutionary algorithms. In the last decade, a growing interest in the integration of Pareto optimality and other evolutionary techniques can be observed. In this work, we integrate EEC, a neuroevolutionary (NE) algorithm, with Pareto optimality. The proposed algorithm is called PEEC. We demonstrate the algorithm on a classic board game, Tic-Tac-Toe, and compare its performance with EEC using three other evaluation models. Our experimental results show that PEEC outperforms all of these and Pareto optimality indeed provides more accurate evaluation to guide NE toward optimal solutions.
The paper is focused on the problem of aggregation of probability distribution applicable for parallel Bivariate Marginal Distribution Algorithm (pBMDA). A new approach based on quantitative combination of probabilistic models is presented. Using this concept, the traditional migration of individuals is replaced with a newly proposed technique of probability parameter migration. In the proposed strategy, the adaptive learning of the resident probability model is used. The short theoretical study is completed by an experimental works for the implemented parallel BMDA algorithm (pBMDA). The performance of pBMDA algorithm is evaluated for various problem size (scalability) and interconnection topology. In addition, the comparison with the previously published aBMDA is presented.
We propose an asynchronous island-model algorithm distribution framework and test the popular Differential Evolution algorithm performance when a few processors are available. We confirm that the island-model introduces the possibility of creating new algorithms consistently going beyond the performances of parallel Differential Evolution multi starts. Moreover, we suggest that using heterogeneous strategies along different islands consistently reaches the reliability and performance of the best of the strategies involved, thus alleviating the problem of algorithm selection. We base our conclusions on experiments performed on high dimensional standard test problems (Rosenbrock 100, Rastrigin 300, Lennard Jones 10 atoms), but also, remarkably, on complex spacecraft interplanetary trajectory optimisation test problems (Messenger, Cassini, GTOC1). Spacecraft trajectory global optimisation problems have been recently proposed as hard benchmark problems for continuous global optimisation. High computational resources needed to tackle these type of problems make them an ideal playground for the development and testing of high performance computing algorithms based on multiple processor availability.
In this paper we present the addition of parameter control in a Differential Evolution algorithm for constrained optimization. Three parameters are self-adapted by encoding them within each individual and a fourth parameter is controlled by a deterministic approach. A set of experiments are performed in order (1) to determine the performance of the modified algorithm with respect to its original version, (2) to analyze the behavior of the self-adaptive parameter values and (3) to compare it with respect to state-of-the-art approaches. Based on the obtained results, some findings regarding the values for the DE parameters as well as for the parameters related with the constraint-handling mechanism are discussed.
Noisy environments are a challenging task for multiobjective evolutionary algorithms. The algorithms may be trapped in local optima or even become a random search in the decision and objective space. In the course of the paper the classical definition of Pareto-dominance is enhanced subject to noisy objective functions in order to make the evolutionary search process more robust and to generate a reliable Pareto front. At each point in the decision space the objective functions are evaluated a fixed number of times and the convex hull of the objective function vectors is computed. Expectation is associated with the median of the objective function va\-lues while uncertainty is reflected by the average distance of the median in each dimension to the points defining the convex hull. By combining these two indicators a new concept of Pareto-dominance is set up. An implementation in NSGA-II and application to test problems show a gain in robustness and search quality.
We extend the Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) by collaborative concepts from Particle Swarm Optimization (PSO). The proposed Particle Swarm CMA-ES (PS-CMA-ES) algorithm is a hybrid real-parameter algorithm that combines the robust local search performance of CMA-ES with the global exploration power of PSO using multiple CMA-ES instances to explore different parts of the search space in parallel. Swarm intelligence is introduced by considering individual CMA-ES instances as lumped particles that communicate with each other. This includes non-local information in CMA-ES in order to improve the search direction and the sampling distribution. We evaluate the performance of PS-CMA-ES on the IEEE CEC 2005 benchmark test suite. The new PS-CMA-ES algorithm shows superior performance on noisy problems and multi-funnel problems with non-convex underlying topology.
Particle Swarm Optimisation (PSO) has been very successful in finding, if not the optimum, at least very good positions in many diverse and complex problem spaces. However, as the number of dimensions of this problem space increases, the performance can fall away. This paper considers the role that the separable nature of the traditional PSO equations may have in this and introduces the ideal of a dynamic momentum value for each dimension as one way of making the PSO equations non-separable. Results obtained using high dimensional versions of a number of traditional functions are presented and clearly show that both the quality of, and the time taken to find, the optimum obtained using variable momentum are better than when using fixed momentum.
This paper introduces a particle swarm optimization algorithm with adaptive velocity (VPSO), in which a moving maximum limited velocity is set in original particle swarm optimization (PSO) algorithm to improve the performance of the PSO. The test results by neural network show that this modified algorithm is better than original PSO in convergent speed and accuracy, and its parameters selection is flexible and is easily realized. The modified algorithm has been applied to fault diagnosis system of neural network for an experimental gearbox, and compared with the PSO and BP algorithm. The conclusion is that VPSO applying to fault diagnosis system not only has higher discrimination for gearbox faults, but also greatly improves the accuracy and efficiency of fault diagnosis.
This paper proposes a PSOAdaBoost algorithm incorporating Particle Swarm Optimization within an AdaBoost framework for face detection applications. The basic component of an AdaBoost detector is a weak classifier, consisting of a feature, selected by an exhaustive search mechanism, and a decision threshold. The proposed PSOAdaBoost computes the best feature and optimizes the threshold in one optimization process. Experiments between the proposed algorithm and AdaBoost (with exhaustive feature selection) suggest that PSOAdaBoost has better performance in terms of much less training time and better classification accuracy.
This paper proposes a novel hybrid algorithm of Particle Swarm Optimization (PSO) and Evolutionary Programming (EP), named Particle Swarm Optimization driven by Evolving Elite Group (PSO-EEG) algorithm. The hybrid algorithm combines the movement update property of canonical PSO with the evolutionary characteristics of EP. It is processed in two stages; elite group stage by EP and ordinary group stage by PSO. For the former group, a novel concept of Evolving Elite Group (EEG) is introduced, which consists of relatively superior particles in a population. The elite particles are evolved by mutation and selection scheme of EP. The other ordinary particles refer to the closest elite particle as well as the global best and the personal best, to update their location. Simulation results demonstrate the proposed PSOEEG is highly competitive in terms of robustness, accuracy and convergence speed for five well-known complex test functions.
In this paper, the DMOEA-DD, which is an improvement of DMOEA[1, 2] by using domain decomposition technique, is applied to tackle the CEC 2009 MOEA competition test instances that are multiobjective optimization problems (MOPs) with complicated Pareto set (PS) geometry shapes. The performance assessment is given by using IGD [3, 4] as performance metric
This paper presents results for the CEC 2009 Special Session on 'Performance Assessment of Constrained / Bound Constrained Multi-Objective Optimization Algorithms' where Generalized Differential Evolution 3 (GDE3) has been used to solve a given set of test problems. The set consist of 23 problems having two, three, or five objectives. Problems have different properties in the sense of separability, modality, and geometry of the Pareto-front According to the results, GDE3 performed well with the most of the problems but performance decreased with a larger number of objectives.
In this paper, the performance assessment of the hybrid Archive-based Micro Genetic Algorithm (AMGA) on a set of bound-constrained synthetic test problems is reported. The hybrid AMGA proposed in this paper is a combination of a classical gradient based single-objective optimization algorithm and an evolutionary multi-objective optimization algorithm. The gradient based optimizer is used for a fast local search and is a variant of the sequential quadratic programming method. The Matlab implementation of the SQP (provided by the fmincon optimization function) is used in this paper. The evolutionary multi-objective optimization algorithm AMGA is used as the global optimizer. A scalarization scheme based on the weighted objectives is proposed which is designed to facilitate the simultaneous improvement of all the objectives. The scalarization scheme proposed in this paper also utilizes reference points as constraints to enable the algorithm to solve non-convex optimization problems. The gradient based optimizer is used as the mutation operator of the evolutionary algorithm and a suitable scheme to switch between the genetic mutation and the gradient based mutation is proposed. The hybrid AMGA is designed to balance local versus global search strategies so as to obtain a set of diverse non-dominated solutions as quickly as possible. The simulation results of the hybrid AMGA are reported on the bound-constrained test problems described in the CEC09 benchmark suite.
Hierarchical menus are now widely used as standard user interfaces in modern applications with GUIs. The menu performance depends on many factors, such as the structure, layout, and colors. There has been extensive research on novel hierarchical menus, but there has been little work on improving performance by optimizing the menu's structure. We have proposed an algorithm based on a genetic algorithm (GA) for optimizing the performance of menus. The algorithm aims to minimize the average selection time of menu items by taking into account movement and decision-making time. We have shown that the proposed algorithm can reduce average selection time nearly 40% for a menu of a cellar phone. But usage pattern were limited and the validation of the model was not confirmed. We will first show the validation result of the model by experiments conducted on PDA. Then we will present results of the performance evaluation of the algorithm by using a wide variety of usage patterns generated by Zipf function. The results show that the model has good accuracy for real users, and the algorithm can attain good results for a wide variety of usage patterns.
A number of population based optimization algorithms have been proposed in recent years to solve unconstrained and constrained single and multi-objective optimization problems. Most of such algorithms inherently prefer a feasible solution over an infeasible one during the course of search which translates to approaching the constraint boundary from the feasible side of the search space. Previous studies [1] have already demonstrated the benefits of explicitly maintaining a fraction of infeasible solutions in Infeasiblity Driven Evolutionary Algorithm (IDEA) for single and multi-objective constrained optimization problems. In this paper, the benefits of IDEA as a sub-evolve mechanism are highlighted for dynamic, constrained single objective optimization problems. IDEA is particularly attractive for such problems as it offers a faster rate of convergence over a conventional EA, which is of significant interest in dynamic optimization problems. The algorithm is tested on two new dynamic constrained test problems. For both the problems, the performance of IDEA is found to be significantly better than conventional EA.
This paper proposes the plateau structure imposed by the Pareto dominance relation as a useful determinant of multiobjective metaheuristic performance. In essence, the dominance relation partitions the search space into a set of equivalence classes, and the probabilities, given a specified neighborhood structure, of moving from one class to another are estimated empirically and used to help assess the likely performance of different flavors of multiobjective search algorithms. The utility of this approach is demonstrated on a number of benchmark multiobjective combinatorial optimization problems. In addition, a number of techniques are proposed to allow this method to be used with larger, real-world problems.
In this paper we discuss the relevance of performing a population dynamics analysis to improve the results obtained using agent-based artificial life systems for optimization. The present study derives from our work trying to solve engineering optimization problems using a distributed approach based on agent's interactions. We have realized that a simple analysis of the population dynamics can show the relevance of some variables and energy exchange rates in the stability of the system. The results obtained can be used to control the equilibrium points and/or avoid non-convergence (population extinctions) by changing the initial conditions or the parameters of the energetic model used in the system. To illustrate the results of such population dynamics analysis, a practical example based on a routing algorithm is presented.
Particle Swarm Optimization (PSO) is a stochastic optimization approach that originated from earlier attempts to simulate the behavior of birds and was successfully applied in many applications as an optimization tool. Estimation of distributions algorithms (EDAs) are a class of evolutionary algorithms which build a probabilistic model capturing the search space properties and use this model to generate new individuals. One research trends that emerged in the past few years is the hybridization of PSO and EDA algorithms. In this work, we examine one of these hybrids attempts that uses a Gaussian model for capturing the search space characteristics. We compare two different approaches, previously introduced into EDAs to prevent premature convergence, when incorporated into this hybrid algorithm. The performance of the hybrid algorithm with and without these approaches are studied using a suite of well-known benchmark optimization functions.
Multiple Offspring Sampling (MOS) is a hybrid algorithm where different evolutionary approaches can coexist simultaneously. The algorithm dynamically evaluates the quality of the solutions produced by each of these algorithms (or techniques, as they are called within MOS) and adjusts their participation in the overall evolutionary process according to this quality value. In this paper we use two alternative measures to evaluate the quality of a reproductive technique and therefore perform the dynamic adjustment of the participation ratios. One of these measures considers the fitness values of the solutions, while the other one determines how difficult the problem is for an evolutionary approach. These two measures are tested and compared over four problems of different complexity and domain (three of them are continuous while the fourth one is discrete). Results show analogies and differences among the used measures and confirm that a good dynamic selection based on a quality measure can boost the performance of the hybrid algorithm.
A major unsolved problem in the field of optimisation and computational intelligence is how to determine which algorithms are best suited to solving which problems. Many of the existing techniques for classifying optimisation problems assume that the problem is encoded using a discrete representation and the results are descriptive rather than analytical. In this paper an information theoretic technique for analysing the ruggedness of a fitness landscape with respect to neutrality was adapted to work in continuous landscapes and to output a single measure of ruggedness. Experiments run on test functions with increasing ruggedness show that the proposed measure of ruggedness produced relative values consistent with a visual inspection of the problem landscapes. A similar approach to the one used in this paper could be used to adapt other measures for characterising discretely encoded problems into approximate measures for characterising real-encoded problems.
RAMP is a rule-based agent for playing Ms. Pac-Man according to the rules stipulated in the 2008 World Congress on Computational Intelligence Ms. Pac-Man Competition. During the competition, our highest score was 15,970, outscoring the eleven other entrants in the competition. In runs reported here, RAMP achieves an average score over 10,000 and a high score of 18,560 across 100 runs; the highest score RAMP has achieved to date is 19,000. These are scores that are better than typical human novice players, including the paper authors themselves. The system was designed to have an evolutionary component, however, this was not developed in time for the competition, which instead used hand-coded rules. We have found the process of tuning the rule sets and accompanying parameters to be a time consuming and inexact process that is expected to benefit from an evolutionary computation approach. This paper describes our initial implementation as well as our progress towards adding an evolutionary computation component to enable the agent learn to play the game.
Beyond its critical role in protein synthesis, RNA has vital structural, functional, and regulatory roles in the cell. The shape of an RNA molecule primarily determines its function in organic systems, so there is notable interest in the computational prediction of RNA structure. Pseudoknots are relatively rare but important structural elements which are difficult to predict computationally. RnaPredict is an evolutionary algorithm (EA) developed for the prediction of RNA secondary structure. This research evaluates RnaPredict after its enhancement with the thermodynamic model from HotKnots, a model specifically designed to compute free energies of structures containing pseudoknots. The performance of the EA is evaluated against the original HotKnots algorithm. RnaPredict significantly improved upon the sensitivity and specificity of structures predicted by HotKnots.
This paper is to investigate the influence of a minimum population size on the performance of the species conservation technique in searching multiple solutions. The species conservation technique is combined a random search technique, which is a special genetic algorithm with one individual, to present an algorithm, called species conservation random search (SCRS), for solving multimodal problems. Each species is built around a dominating point, called the species seed, with a given species radius, and the species are saved in the species set. The random search is used to explore a new point in the neighborhood area of an initial point randomly selected from the species set. A modified species conservation technique has been developed to update species seeds according to these new exploration points. Numerical experiments demonstrate that the proposed SCRS is very effective in dealing with multimodal problems and can also find all the global solutions of test functions.
This paper present a novel and scrutinized parametric modeling of a laboratory scaled helicopter that is a twin rotor multi input multi output system (TRMS) by employing a real-coded genetic algorithm technique. The main goal for this work is to emphasis the potential benefits of this architecture for real system identification. Instead of working on the conventional bit by bit operation, both the crossover and mutation operators are real-value handled. The effectiveness of the proposed algorithm is demonstrated by comparison to a binary-coded GA based on the TRMS approach. A complete system identification procedure has been carried out, from experimental design to model validation using a laboratory-scale helicopter. In this case, the identified model is characterized by a fourth order linear ARMAX structure which describes with very high precision the hovering motion of a TRMS. The TRMS can be perceived as a static test rig for an air vehicle with formidable control challenges. Therefore, an analysis in modeling of nonlinear aerodynamic function is needed and carried out in both time and frequency domains based on observed input and output data. Experimental results are obtained using a laboratory set-up system, confirming the viability and effectiveness of the proposed methodology.
In this paper we wish to investigate how optimization problems involving angles can best be handled when using Differential Evolution (DE) as the optimization technique. Specifically we state the hypothesis that angles should not be recombined naivly. To investigate this hypothesis we define two simple optimization problems involving angles and investigate our hypothesis on these by creating two angle recombination strategies for the DE algorithm. Our hope is that real world problems containing angles can benefit from this study, and we therefore test our hypothesis on a problem from the field of computational chemistry.
An evolutionary algorithm automatically discovers suitable solutions to a problem, which may lie anywhere in a large search space of candidate solutions. In the case of Genetic Programming, this means performing an efficient search of all possible computer programs represented as trees. Exploration of the search space appears to be constrained by structural mechanisms that exist in Genetic Programming as a consequence of using trees to represent solutions. As a result, programs with certain structures are more likely to be evolved, and others extremely unlikely. We investigate whether the graph representation used in Cartesian Genetic Programming causes an analogous biasing effect, imposing natural limitations on the class of solution structures that are likely to be evolved. Representation bias and structural bias are identified: the rarer 'regular' structures appear to be easier to evolve than more common 'irregular' ones.
Human beings learn to do a task and then go on to learn some other task. However, they do not forget the previous learning. If need arises, they can call upon their previous learning and do not have to relearn from scratch again. In this paper, we build upon our earlier work in which we presented a mechanism for learning multiple tasks in a dynamic environment where the tasks can change arbitrarily without any warning to the learning agents. The main feature of the mechanism is that a percentage of the learning agents is periodically made to reset its previous learning and restart learning again. Thus, there is always a sub-population which can learn the new task, whenever there is a task change, without being hampered by previous learning. The learning then spreads to the other members of the population also. In our current work we experiment with the incorporation of archive for preserving those strategies which have performed well. The strategies in the archive are tested time to time in the current environment. If the current task is the same as the task for which the strategy was first discovered, then that strategy rapidly comes in vogue for the whole population. The criteria by which strategies are selected for storage in the archive, the deletion of some strategies because the archive has limited space and the mechanism for selecting strategies for utilization in the current environment are presented.
It is generally challenging to design decentralized controllers for swarms of robots because there is often no obvious relation between the individual robot behaviors and the final behavior of the swarm. As a solution, we use artificial evolution to automatically discover neural controllers for swarming robots. Artificial evolution has the potential to find simple and efficient strategies which might otherwise have been overlooked by a human designer. However, evolved controllers are often unadapted when used in scenarios that differ even slightly from those encountered during the evolutionary process. By reverse-engineering evolved controllers we aim towards hand-designed controllers which capture the simplicity and efficiency of evolved neural controllers while being easy to optimize for a variety of scenarios.
Univariate Marginal Distribution Algorithms (UMDAs) are a kind of Estimation of Distribution Algorithms (EDAs) which do not consider the dependencies among the variables. In this paper, on the basis of our proposed approach in [1], we present a rigorous proof for the result that the UMDA with margins (in [1] we merely showed the effectiveness of margins) cannot find the global optimum of the TRAPLEADINGONES problem [2] within polynomial number of generations with a probability that is super-polynomially close to 1. Such a theoretical result is significant in sheding light on the fundamental issues of what problem characteristics make an EDA hard/easy and when an EDA is expected to perform well/poorly for a given problem.
The problem of optimal mutual fund investment taking into account possible risks is considered. In this paper we consider lost profit in the growing market and a loss in a falling market as a possible risk. Our studies show that the efficiency of mutual funds can be estimated by nine main parameters obtained by historical data. Evaluation and ranking criteria sets for mutual funds are defined by the help of Kohonen Self-Organizing Maps. We propose to use a simplified ranking consisting of five categories. The methodology of constructing optimal strategies for risk-sensitive portfolio optimization is proposed. The performance of constructed portfolio is superior to the most mutual funds and other portfolios. The proposed methodology underwent a test for last four years and showed high efficiency and robustness both in growing and falling (during current world financial crisis) markets.
In this work, we describe a learning system that uses the CMA-ES method from evolutionary computation to optimize the morphology and the walking patterns for a complex legged robot simultaneously. Using simulation tools has the advantage that an optimization of robot morphology is possible before actually building the robot. Also, manually developing walking patterns for kinematically complex robots can be a challenging and time-consuming task. Both, the walking pattern and the morphology depend highly on each other to produce an energy-efficient and stable locomotion behaviour. In order to automate this design process, a learning system that generates, tests, and optimizes different walking patterns and morphologies is needed, as well as the ability to accurately simulate a robot and its environment. The evolutionary algorithm optimizes parameters that affect the trajectories of the robot's foot points, testing the resulting walking patterns in a physical simulation. The robot's limbs are controlled using inverse kinematics. In the future, the best solution evolved by this approach will be used for the mechanical construction of the real robot. Afterwards, the optimized walking patterns will be transferred to the real robot.
The cognition of robots is not complete due to noises in environments, so environments are uncertain for robots. We present a method for robot path planning based on uncertain environments using particle swarm optimization. Firstly, we describe and deal with the uncertainties in the environment during the path planning, and the global environment model is constructed based on these uncertainties. And then the globally optimal path is generated by using particle swarm optimization, whose structure is used to meet the constrains. Finally, with the cognition of robot becoming clear during the robot moving along the global path, local strategies are adopted to handle the new cognitive information. The simulation results show the feasibility and efficiency of the proposed method.
In many practical applications it is observable that optimal solutions are vulnerable to changes in environmental- or decision-variables and therefore become suboptimal or even infeasible in uncertain environments. Solutions immune or less vulnerable to such uncertainties are called robust. In this paper we present and compare two algorithms for creating robust solutions to the vehicle routing problem with time-windows (VRPTW) in which travel times are uncertain. In the first approach robustness is defined as a dedicated optimization objective and the NSGA2 algorithm is used to solve the VRPTW as a multi-objective optimization problem. A Pareto-front is generated that displays the trade-off between robustness and the total distance to be minimized. A second approach uses a modified predator-prey algorithm, that implicitly takes robustness into account by defining different travel-time-matrices for each predator. It can be shown that the predator-prey approach is much faster than the NSGA2 and still delivers viable results.
The problem of how to create NPC AI for videogames that believably imitates particular human players is addressed. Previous approaches to learning player behaviour is found to either not generalize well to new environments and noisy perceptions, or to not reproduce human behaviour in sufficient detail. It is proposed that better solutions to this problem can be built on multiobjective evolutionary algorithms, with objectives relating both to traditional progress-based fitness (playing the game well) and similarity to recorded human behaviour (behaving like the recorded player). This idea is explored in the context of a modern racing game.
A genetic algorithm (GA) presents an excellent method for controller parameter tuning. In our work, we evolved the heading as well as the altitude controller for a small lightweight helicopter. We use the real flying robot to evaluate the GA's individuals rather than an artificially consistent simulator. By doing so we avoid the "reality gap", taking the controller from the simulator to the real world. In this paper we analyze the evolutionary aspects of this technique and discuss the issues that need to be considered for it to perform well and result in robust controllers.
This study explores the ability of dynamic polyominos to acquire different types of robustness in a variety of environments. A polyomino is a collection of identical squares joined along their sides to form a connected shape. This study introduces a cellular encoding for polyominos that grow in a manner that adapts to environmental obstructions. Fitness evaluation places polyominos in competition to occupy space with each square of a grid occupiable by only a single individual. Evolved polyomino genes are studied for their robustness to choice of opponent and environment. This study is part of a series studying the evolution of robustness, enlarging the scope of the series to include robustness against choice of opponent and environment. Polyomino fitness is evaluated in monoculture, multiculture, and obstructed environments. It is found that in all cases added time evolving grants a greater degree of robustness than the other possible sources of robustness. When polyomino genes have been evolved for comparable amounts of time it is found those with competitive fitness evaluation are superior. When the impact of environmental obstructions are considered it is found that being in your home environment grants a competitive advantage, though not as strong of an advantage as added evolution, with a single exception.
The paper proposes a novel formulation of the classical box-pushing problem by mobile robots as a multi-objective optimization problem, and presents Pareto optimal solution to the problem using Non-dominated Sorting Genetic Algorithm-II (NSGA-II). The proposed method adopts local planning scheme, and allows both turning and translation of the box in the robots' workspace in order to minimize the consumption of both energy and time. The planning scheme introduced here determines the magnitude of the forces applied by two mobile robots at specific location on the box in order to align and translate it along the time- and energy- optimal trajectory in each distinct step of motion of the box. The merit of the proposed work lies in autonomous selection of translation distance and other important parameters of the robot motion model using NSGA-II. The suggested scheme, to the best of the authors' knowledge, is a first successful realization of a communication-free, centralized cooperation between two robots used in box shifting problem satisfying both time and energy minimization objectives simultaneously, presuming no additional user-defined constraint on the selection of linear distance traversal.
This paper presents an investigation into the scalability of the vector-based PSO, a niching algorithm using particle swarm optimization. The vector-based PSO locates and maintains niches by using vector operations to determine niche boundaries. The technique builds upon existing knowledge of the particle swarm in such a way that the swarm can be organized into subswarms without prior knowledge of the number of niches in the search space and the corresponding niche radii, thus reducing the number of user-specified parameters. In a designated search space a linear increase in the number of dimensions often results in an exponential or near exponential increase in the number of optima. Empirical results are reported where the vector-based PSO is tested on three multimodal functions in one to four dimensions using a range of swarm sizes. Optimal swarm sizes are derived where all or most of the optima should be located.
Landing on distant planets is always a challenging task due to the distance and hostile environments found. In the design of autonomous hazard avoidance systems we find the particularly relevant task of landing site selection, that has to operate in real-time as the lander approaches the planet's surface. Seeking to improve the computational complexity of previous approaches to this problem, we propose the use of non-exhaustive search methodologies. A comparative study of several algorithms, such as Tabu Search and Particle Swarm Optimization, was performed. The results are very promising, with Particle Swarm Optimization showing the capacity to consistently produce solutions of very high quality, on distinct landing scenarios.
Self Modifying CGP (SMCGP) is a developmental form of Cartesian Genetic Programming(CGP). It differs from CGP by including primitive functions which modify the program. Beginning with the evolved genotype the self-modifying functions produce a new program (phenotype) at each iteration. In this paper we have applied it to a well known digital circuit building problem: even-parity. We show that it is easier to solve difficult parity problems with SMCGP than either with CGP or Modular CGP, and that the increase in efficiency grows with problem size. More importantly, we prove that SMCGP can evolve general solutions to arbitrary-sized even parity problems.
In an attempt to address the scaling up of genetic programming to handle complex problems, we have proposed a hierarchical approach in which programs are formed from independently evolved code fragments, each of which is responsible for handling a subset of the test input cases. Although this approach offers substantial performance advantages in comparison to more conventional systems, the programs it evolves exhibit some undesirable properties for certain problem domains. We therefore propose the introduction of a self-adaptive mechanism that allows the system dynamically to focus evolutionary effort on the program components most in need. Experimentation reveals that not only does this technique lead to better-behaved programs, it also gives rise to further significant performance improvements.
Living organisms are endowed with three structural principles: multicellular architecture, cellular division, and cellular differentiation. Implemented in digital according to these principles, our bit slice processors present self-organizing mechanisms like configuration, cloning, cicatrization, and regeneration. These mechanisms are made of simple processes such as growth, load, branching, repair, reset, and kill. The description of a configurable molecule implementing the self-organizing mechanisms and its application to an arithmetic and logic unit constitute the core of this paper.
Using semantic analysis, we present a technique known as semantically driven mutation which can explicitly detect and apply behavioural changes caused by the syntactic changes in programs that result from the mutation operation. Using semantically driven mutation, we demonstrate increased performance in genetic programming on seven benchmark genetic programming problems over two different domains.
Support Vector Machines (SVMs) are considered state-of-the-art learning machines techniques for classification problems. This paper studies the training of SVMs in the special case of problems in which the raw data to be used for training purposes is composed of both labeled and unlabeled data - the semi-supervised learning problem. This paper proposes the definition of an intermediate problem of attributing labels to the unlabeled data as a multiobjective optimization problem, with the conflicting objectives of minimizing the classification error over the training data set and maximizing the regularity of the resulting classifier. This intermediate problem is solved using an evolutionary multiobjective algorithm, the SPEA2. Simulation results are presented in order to illustrate the suitability of the proposed technique.
For biomedical researchers it is now possible to measure large numbers of DNA sequence variations across the human genome. Measuring hundreds of thousands of variations is now routine, but single variations which consistently predict an individual's risk of common human disease have proven elusive. Instead of single variants determining the risk of common human diseases, it seems more likely that disease risk is best modeled by interactions between biological components. The evolutionary computing challenge now is to effectively explore interactions in these large datasets and identify combinations of variations which are robust predictors of common human diseases such as bladder cancer. One promising approach to this problem is genetic programming (GP). A GP approach for this problem will use darwinian inspired evolution to evolve programs which find and model attribute interactions which predict an individual's risk of common human diseases. The goal of this study is to develop and evaluate two initializers for this domain. We develop a probabilistic initializer which uses expert knowledge to select attributes and an enumerative initializer which maximizes attribute diversity in the generated population. We compare these initializers to a random initializer which displays no preference for attributes. We show that the expert-knowledge-aware probabilistic initializer significantly outperforms both the random initializer and the enumerative initializer. We discuss implications of these results for the design of GP strategies which are able to detect and characterize predictors of common human diseases.
In this paper we develop and test a novel stochastic algorithm SNE (Shrinking Neighborhood Evolution) based on the issue of bound constrained optimization problem. Its heuristic strategy is simple and direct-related to the solving problem based on the concept of "k-box-neighborhood" -defined in this paper. Our numerical experiments show that the optimization capability of SNE is competing to other congeneric algorithms such as Particle Swarm Optimizor (PSO), Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) and Differential Evolution (DE). The new method requires few control parameters, easy to use, and has promising potentials to parallel computation.
In this work new improvements from a previous approach of an Automatic Design of Artificial Neural Networks applied to forecast time series is tackled. The automatic process to design Artificial Neural Networks is carried out by a Genetic Algorithm. These improvements, in order to get an accurate forecasting, are related with: to shuffle train and test patterns obtained from time series values and improving the fitness function during the global learning process (i.e. Genetic Algorithm) using a new patterns set called validation apart of the two used till the moment (i.e. train and test). The object of this study is to try to improve the final forecasting getting an accurate system. Results of the Artificial Neural Networks got by our system to forecast a set of famous time series are shown
The flexible architecture of evolutionary algorithms allows specialised models to be obtained with the aim of resembling other algorithms, but performing more satisfactorily. In fact, several evolutionary proposals playing the role of local search methods have been proposed in the literature. In this paper, we make a step forward extending an innovative model recently proposed, which performs local search on external solutions, to match search process carried out by simulated annealing. We introduce acceptance criterion and cooling scheme concepts from simulated annealing, and modify some original components to better suit the new search process performed. An empirical study comparing the new model with classical simulated annealing algorithms shows that 1) the proposal is often able to reach good fitness values before than its competitors and 2) it suffers weaker convergence speed reductions that allow it to fruitfully continue the search process.
A novel real-parameter Quantum Evolutionary Algorithm is presented. The algorithm pieces together ideas from EA and Quantum Computing to provide a robust technique that can be utilized to optimize even highly constrained non-linear functions with real parameters. Economic Load Dispatch (ELD) and Reactive Power Dispatch (RPD) are two important problems in power systems that are modeled using nonlinear, discontinuous objective functions and constraints. The proposed method has been applied to these problems and its performance is found to be better than other methods
The new hp--HGS multi-deme, genetic strategy(hp-adaptive Finite Element Method combined with Hierarchic Genetic Strategy)for economic solving parametric inverse problems is presented in this paper. Inverse problems under consideration are formulated as the global optimization ones, where the objective is to express the discrepancy between the computed and measured energy. The efficiency of the proposed strategy results from coupling an adaptative accuracy of solving optimization problems with the accuracy of hp--FEM problem solver. The paper briefly reports the results of the asymptotic analysis that ensures the global search possibility and allows to compare the efficiency with the single population algorithm as well as with the instance of HGS without adaptation of the direct solver accuracy. A computational example shows the course of tuning the hp--FEM strategy for the simple L-shape domain benchmark.
This paper proposes a PSO-FFPP algorithm based on the particle swarm optimization (PSO) framework to solve the flight frequency programming problem (FFPP). The FFPP is to determine the flight frequency for each type of aircraft on each flight route. This problem is fundamental to an airline's operational planning because it affects the airline's profit and market share greatly. The FFPP can be formulated as an integer programming problem with constraints that is very suitable to be solved by the PSO algorithm. The proposed PSO-FFPP algorithm codes the decision variables of the FFPP with real number to represent the potential solutions and defines the optimization objective as a maximization problem for the airlines profit. A constraints handling method that combines the ideas of feasible solution preserving and infeasible solution rejection is developed. This method avoids the expense of infeasibility repair or penalty, making the algorithm simple to use and easy to extend. An integer handing process is also devised to round the real number to the nearest valid integer before feasibility check and function evaluation. This process maintains the search tendency of the PSO algorithm and can help to search in a promising region for the global optimum. The feasibility of the proposed algorithm is demonstrated and compared with the Monte Carlo method and the enumeration method on a simulation case with promising results. Experiments are also conducted to investigate the factors that affect the solution quality and computational time.
Neural networks (NNs) were evolved to learn to play the zero-sum game Othello (also known as reversi) without relying on a-priori or expert knowledge. Such neural networks were able to discover game-playing strategies through co-evolution, where the neural networks just play against themselves across generations. The effect of the spatial processing layer on evolution was investigated. It was found that the evolutionary process was crucially dependent on the way in which spatial information was presented. A simple sampling pattern based on the squares attacked by a single queen in Chess resulted the networks converging to a solution in which the majority of networks, handicapped by playing Black and playing without using any look-ahead algorithm, could defeat a positional strategy using look-ahead at ply-depth=4 and a piece-differential strategy using look-ahead at ply-depth=6. Improvement and convergence was observed to be accompanied by an gradual increase in the survival time of neural network strategies from less than 10 generations to about 600 generations. Surprisingly, evolved neural networks had difficulty in defeating a simple mobility strategy playing at a ply-depth=2. This work suggests that in deciding a suitable way to spatially sample a board position, it is important to consider the rules of the game.
SpiNDeK (Spiking Neural Network Design Kit) is an integrated design tool intended to support the development of emulation of complex bioinspired neural networks. In this work, the most relevant aspects of the tool are reported, regarding the generation of connections as well as synapse and neuron parameters of spiking neural networks as well as the automated code generation and simulation, ready to be executed by an ad-hoc parallel architecture. The tool is fully functional and has demonstrated its usefulness.
Structure learning is a crucial component of a multivariate Estimation of Distribution algorithm. It is the part which determines the interactions between variables in the probabilistic model, based on analysis of the fitness function or a population. In this paper we take three different approaches to structure learning in an EDA based on Markov networks and use measures from the information retrieval community (precision, recall and the F-measure) to assess the quality of the structures learned. We then observe the impact that structure has on the fitness modelling and optimisation capabilities of the resulting model, concluding that these results should be relevant to research in both structure learning and fitness modelling.
Repulsive interactions of black garden ants (Lasius Niger) has been found to be critical for preventing congestion and maintaining optimal food return rate in ant colony. Previously, mathematical models have been built to study the effect of the repulsive interactions on the path selection decision of ants. However, the detailed mechanisms behind the interactions are still poorly understood. For the first time, we developed an evolvable individual-based model to simulate foraging ants with the repulsive interactions, to investigate the underlying mechanisms and its effects on the overall food return rate of the ant colony. We employed a two-phase evolutionary process using a Genetic Algorithm: we firstly evolved a model with trail following behaviour in an open environment in order to make this behaviour more biologically realistic. Then based on the evolved model, the repulsive interactions were introduced and evolved on a double-bridge environment in order to get an optimal effect on the food return rate in crowded situation. Our model is sufficient enough to reveal the details of the possible underlying mechanisms of the repulsive interactions and its effect on the transportation efficiency.
With the development of Graphics Processing Units (GPU) and the Compute Unified Device Architecture (CUDA) platform, several areas of knowledge are being benefited with the reduction of the computing time. Our goal is to show how optimization algorithms inspired by Swarm Intelligence can take profit from this technology. In this paper, we provide an implementation of the Particle Swarm Optimization (PSO) algorithm in C-CUDA. The algorithm was tested on a suite of well-known benchmark optimization problems and the computing time has been compared with the same algorithm implemented in C and Matlab. Results demonstrate that the computing time can significantly be reduced using C-CUDA. As far as we know, this is the first implementation of PSO in C-CUDA.
One of the main aspects of the 'SYMBRION' and 'REPLICATOR' projects is that the robots can aggregate o form a multi-robot organism. For this reason the control mechanisms have to be able to control a single robot, a swarm of robots or an aggregated collective organism. To break down the complexity of development and to take the interaction with the environment and other robots into account, bio-inspired and evolutionary concepts are applied. In this paper we describe the underlying software architecture for the projects to enable different controller types, evolution and learning.
Using a game-theoretic model combined with the evolutionary model, we investigate the conditions under which the desirable interaction rules will evolve and sustain in various social interaction settings. The direction of the research to come is to understand how the interaction structure, the network topology, determines the path of evolutionary dynamics. For the emergence of desirable outcomes at the macroscopic level, the patterns of social interaction are critical. We find that the efficient and fair outcome emerges relatively quickly in symmetric networks where each agent plays the game with the same number of players. In symmetric networks, agents appear to easily recognize the possibility of a coordinated turn-taking behavior or alternating reciprocity as a means to generate an efficient and fair outcome.
This paper proposes a way to model uncertainties and to introduce them explicitly in the design process of a preliminary space mission. Traditionally, a system margin approach is used in order to take them into account. In this paper, \et{} is proposed to crystallise the inherent uncertainties. The design process is then formulated as an Optimisation Under Uncertainty (OUU) problem. Two evolutionary multi-objective approaches are used to solve the OUU, a bi-objective formulation and a complete belief function optimisation. The BepiColombo mission is used as a test case to investigate the benefits of the proposed method and to compare the two approaches mentioned.
This paper attempts to address the question of scaling up PSO algorithms to high dimensional optimization problems. We present a cooperative coevolving PSO (CCPSO) algorithm incorporating random grouping and adaptive weighting, two techniques that have been shown to be effective for handling high dimensional nonseparable problems. The proposed CCPSO algorithms outperformed a previously developed coevolving PSO algorithm on nonseparable functions of 30 dimensions. Furthermore, the scalability of the proposed algorithm to high dimensional nonseparable problems (of up to 1000 dimensions) is examined and compared with two existing coevolving DE algorithms, and new insights are obtained. Our experimental results show the proposed CCPSO algorithms can perform reasonably well with only a small number of evaluations. The results also suggest that both the random grouping and adaptive weighting schemes are viable approaches that can be generalized to other evolutionary optimization methods.
The uncertainty in many engineering problems can be handled through probabilistic, fuzzy, or interval methods. This paper aims to use a hybrid genetic algorithm for tackling such problems. The proposed hybrid algorithm integrates a simple local search strategy as the worst-case-scenario technique of anti-optimization with a constrained multi-objective evolutionary algorithm. The work demonstrates the use of a technique alternating between optimization (general GA) and anti-optimization (local search). Local search utilizes specialized search engines that allow users to submit constrained searches. The algorithm has been tuned and its performance evaluated through specially formulated test problems referred to as 'Target Matching Problems' with multiple objectives. The results obtained indicate that the approach can produce good results at reasonable computational costs.
Many researchers have encountered the problem that the evolution of electronic circuits becomes exponentially more difficult when problems with an increasing number of outputs are tackled. Although this is an issue in both intrinsic and extrinsic evolution experiments, overcoming this problem is particularly challenging in the case of evolvable hardware, where logic and routing resources are constrained according to the given architecture. Consequently, the success of experiments also depends on how the inputs and outputs are interfaced to the evolvable hardware. Various approaches have been made to solve the multiple output problem: partitioning the task with respect to the input or output space, incremental evolution of sub-tasks or resource allocation. However, in most cases, the proposed methods can only be applied in the case of extrinsic evolution. In this paper, we have accordingly, focused on scaling problem of increasing numbers of outputs when logic circuits are intrinsically evolved. We raise a number of questions: how big is the performance drop when increasing the number of outputs? Can the resources of evolvable hardware be structured in a suitable way to overcome the complexity imposed by multiple outputs, without including knowledge about the problem domain? Can available resources in hardware still be efficiently used when pre-structured? In order to answer these questions, different structural implementations are investigated. We have looked at these issues in solving three problems: 4-bit parity, 2-bit adder and 2-bit multiplier.
EvRFind is an application used for the task of rule discovery in data mining. This paper describes various techniques used by EvRFind to enhance an evolutionary search for the purpose of rule discovery. Although some of the techniques are non-evolutionary by design, these still rely on evolution to guide the process. Results of experiments are compared to those found in other published work.
Abstract—The clock-proxy auction is a combinatorial auction which is specially designed for environments where bidders have complex preference structures (complements and substitute items), as also occurs in the spectrum licenses market. In such an intricate context, it is difficult to find an optimal strategy. Nevertheless, if a particular environment is selected, evolutionary computation techniques can be used to find some bidding patterns. This research focuses on the sale of a portion of the spectrum called "digital dividend", implementing a realistic model that could fit in most European countries. To this end, a simulator of the auction mechanism is created and a set of candidate bidding strategies are implemented. Subsequently, the developed GA tests the proposed strategies, searching for the behavior that maximizes the average profits for one bidder. Finally, the results are supported by an exhaustive validation test bed.
Many real-world problems are dynamic, requiring an optimization algorithm which is able to continuously track a changing optimum over time. In this paper, we present a stigmergy-based algorithm for solving optimization problems with continuous variables, labeled Differential Ant-Stigmergy Algorithm (DASA). The DASA is applied to dynamic optimization problems without any modification to the algorithm. The performance of the DASA is evaluated on the set of benchmark problems provided for CEC'2009 Special Session on Evolutionary Computation in Dynamic and Uncertain Environments.
Operation of developmental systems is in many ways similar to that of discrete dynamic networks. Applying such network analysis to developmental system enables investigation of the dynamic properties of development at different levels. In this work the basins of attraction of a developmental system is explored in order to gain information about the details from the interwoven nature of the development of structure and behaviour. The investigation show how such method of analysis can offer insight about the workings of developmental systems.
Multi-classifier systems, also known as ensembles or committees, have been widely used to solve several classification problems, because they usually provide better performance than the individual classifiers. However, in order to build robust ensembles, it is necessary that the individual classifiers are as accurate as diverse among themselves – this is known as the diversity/accuracy dilemma. In this sense, some works analyzing the ensemble performance in context of this dilemma have been proposed. However, the majority of them address the homogenous structures of ensemble, i.e., ensembles composed only of the same type of classifiers. Thus, motivated by this limitation, this paper will perform an empirical investigation on the diversity/accuracy dilemma for heterogeneous ensembles. In order to do this, genetic algorithms will be used to guide the building of the ensemble systems. I.
We explore a simple genetic algorithm (GA) in which two different fitness functions are combined and used together in an epoch of preadaptation prior to an epoch involving only one of the fitness functions. The effects of preadaptation epoch length on mean best-of-run fitness and success rate statistics are examined and contrasted with those of an otherwise identical GA using no preadaptation. The results show that, for this problem at least, the right amount of preadaptation can be very beneficial, and that both too much and too little preadaptation can be detrimental (as opposed to merely less beneficial).
Specialization, or division of labour, leads to increased productivity in systems. We study the effect of social influence on the level of agent specialization in complex systems connected via social networks. There are several methods that explain the emergence of specialization, with the most prominent being the genetic threshold model. This model posits that agents possess an inherent threshold for task stimulus, and when that threshold is exceeded, the agent will perform that task. The idea of social influence is that an agent's choice of which task to specialize in when multiple ones are availabe, is influenced by the choices of its neighbours. Using the threshold model and an established metric that quantifies the level of agent specialization, we found that social influence leads to an increase in the division of labour.
Recently, fourth party logistics (4PL) is receiving more and more attentions in manufacturing and retail industries. However, the research on the fourth party logistics routing problems (4PLRP) has just begun. There is a little research on how to quantify and modeling the fourth party logistics optimization, design the algorithms to solve it. In this paper, the mathematical model of the point to point single task path optimization of 4PLRP with time windows (4PLRPTW) is established based on multi-graph, which the objective is to find minimum cost routes from the start node to the destination node within the pre-specified time windows. A recently-developed meta-heuristic optimization method, harmony search, imitating the music improvisation process where musicians improvise their instruments' pitches searching for a perfect stare of harmony is suggested for solving 4PLRPTW. The results of the numerical experiments demonstrate that the harmony search is effective and could find near optimal solution within the reasonable amount of time and computation.
This paper investigates the role of genotypic search space dimensionality on the behaviour and characteristics of a computational model of embryogeny. By varying genome length, it is shown that genotype dimensionality can have an impact on the performance of an evolutionary process and the origins of this are discussed. Observed characteristics of robustness, scalability and modularity are shown to be retained.
Traditionally, the uncapacitated facility location problem (UFLP) is solved as a single-objective optimization exercise, and focusses on minimizing the cost of operating a distribution network. This paper presents an exploratory study in which the environmental impact is modelled as a separate objective to the economic cost. We assume that the environmental cost of transport is large in comparison to the impact involved in operating distribution centres or warehouses (in terms of CO2 emissions, for example). We further conjecture that the whole impact on the environment is not fully reflected in the costs incurred by logistics operators. Based on these ideas, we investigate a number of "what if ?" scenarios, using a Fast Non-Dominated Sorting Genetic Algorithm (NSGA-II), to provide sets of non-dominated solutions to some test instances. The analysis is conducted on both two-objective (economic cost versus environmental impact) and three objective (economic cost, environmental impact and uncovered demand) models. Initial results are promising, indicating that this approach could indeed be used to provide informed choices to a human decision maker.
This paper presents a critical analysis of the Pareto-Following Variation Operator (PFVO) when used as an approximation method for Multiobjective Evolutionary Algorithms(MOEA). In previous work, we have described the development and implementation of the PFVO. The simulation results reported indicated that when the PFVO was integrated with NSGA-II there was a significant increase in the convergence speed of the algorithm. In this study, we extend this work. We claim that when the PFVO is combined with any MOEA that uses a non-dominated sorting routine before selection, it will lead to faster convergence and high quality solutions. Numerical results are presented for two base algorithms: SPEA-II and RM-MEDA to support are claim. We also describe enhancements to the approximation method that were introduced so that the enhanced algorithm was able to track the Pareto-optimal front in the right direction
This paper describes the idea of MOEA/D and proposes a strategy for allocating the computational resource to different subproblems in MOEA/D. The new version of MOEA/D has been tested on all the CEC09 unconstrained MOP test instances.
In this paper a new idea to solve the traveling salesman problem is introduced. The idea is categorized within meta-heuristic evolutionary algorithms and is based on a normal wise human-being thinking method. Starting from an arbitrary starting point, three factors are considered to generate a score vector by which the next position is selected. Distance from the non-visited points, successful previous experiments, and a randomly changing factor are the components that make the score vector. The effect of each factor can be adjusted by a weighting parameter. The algorithm is implemented and tested on many small (less than 100 cities) benchmarks. The primary surprising results obtained by this soft computing approach, in comparison to many other recently developed methods, turn a light on its bright perspective to be known as an efficient simple solution to the problem.
Humans are inclined to engage in long-lasting relationships whose stability does not only rely on cooperation, but often also on loyalty --- our tendency to keep interacting with the same partners even when better alternatives exist. Yet, what is the evolutionary mechanism behind such irrational behavior? Furthermore, under which conditions are individuals tempted to abandon their loyalty, and how does this affect the overall level of cooperation? Here, we study a model in which individuals interact along the edges of a dynamical graph, being able to adjust both their behavior and their social ties. Their willingness to sever interactions is determined by an individual characteristic and subject to evolution. We show that defectors ultimately loose any commitment to their social contacts, a result of their inability to establish any social tie under mutual agreement. Ironically, defectors' constant search for new partners to exploit leads to heterogeneous networks in which cooperation survives more easily. Cooperators, on the other hand, develop much more stable and long-term relationships. Their loyalty to their partners only decreases when the competition with defectors becomes fierce. These results indicate how our innate commitment to partners is related to mutual agreement among cooperators and how this commitment is evolutionary disadvantageous in times of conflict, both from an individual and a group perspective.
A series of numerical experiments using a co-evolutionary model for both networks and strategies for 2 x 2 games was carried out. It was proven that there was an interesting relation between assortative mixing of the evolved network and emerging cooperation. In the Prisoner's Dilemma (PD) game class, the evolutionary trail for a weak dilemma game leads to an assortative mixing network, and attains cooperative situation easily. A game implemented with a stronger dilemma, however, makes the network very heterogeneous, featuring a negative assortative coefficient to solve the dilemma situation. This implies that the dilemma strength in PD significantly affects the direction the assortative coefficient takes during evolutionary processes in the co-evolution model.
Evaluating conflict resolution algorithms in the air-traffic domain is a challenging task. These algorithms are usually tested using a pair of aircraft or a limited number of geometries involving multiple aircraft. Our previous work demonstrated the use of evolutionary computation for risk assessment of air-traffic conflict detection algorithms using a red-teaming (or playing the devil) approach. This paper extends our previous work to conflict resolution and investigate the effect of symmetry in the representation on the performance of the evolutionary operators. Scenarios for testing air traffic conflict detection and resolution algorithms are each represented by a chromosome, which itself represents a group of pairs of aircraft in conflict. Each paired-conflict comes with its own set of parameters. However, any shuffling of the pairs does not change the definition of a scenario. If we have N pairs, any of the N! shuffles maps to the same phenotype. Therefore, there is high level symmetry in this problem. Because of the finite population size used in an evolutionary algorithm, one may expect that by fixing the position of each pair on the chromosome, a crossover operator that relies on the position of each gene is probably going to be inferior to one that does not. In this paper, we demonstrate, using a genetic algorithm, that - despite the high level symmetry in this problem - a position-dependent crossover is better than a position-independent crossover. This counterintuitive result identifies a potential efficient parameter setup for our future experiments in this problem domain.
Concurrent process-oriented programming is a natural medium for simulating complex systems, particularly systems where many simple components interact in an environment (which may itself be complex). There is little guidance for engineering complex systems simulation. In the context of simulation work to support immunological research, we explore relevant approaches to modelling, and draw on concepts from dependable and high-integrity systems engineering, including the emphasis on the need to validate all aspects of the simulation.
By dividing the multiobjective optimization of the decision space into several small regions, this paper proposes multi-objective optimization algorithm based on sub-regional search, which make individuals in same region operate each other by evolutionary operator and the information between the individuals of different regions exchange through their offsprings re-divided into regions again. Since the proposed algorithm uses the sub-regional search, the computational complexity at each generation is lower than the NSGA-II and MSEA. The proposed algorithm uses the max-min strategy with determined weights as fitness functions, which make it approach evenly distributed solution in Pareto front. This paper presents a kind of easy technology dealing with the constraint, which makes the proposed algorithm solved unconstrained multiobjective problems can also be used to solve constrained multiobjective problems. The numerical results, with 13 unconstrained multiobjective optimization testing instances and 10 constrained multiobjective optimization testing instances, are shown in this paper.
Parameter setting is an important issue in the design of evolutionary algorithms. Recently, experimental work has pointed out that it is often not useful to work with a fixed mutation rate. Therefore it was proposed that the population be ranked according to fitness and the mutation rate of an individual should depend on its rank. The claim is that this allows the algorithm to explore new regions in the search space as well as progress quickly towards optimal solutions. Complementing the experimental investigations, we examine the proposed approach by presenting rigorous theoretical analyses which point out the differences of rank-based mutation compared to a standard approach using a fixed mutation rate. To this end we theoretically explain the behaviour of rank-based mutation on various fitness landscapes proposed in the experimental work and present new significant classes of functions where the use of rank-based mutation may be both beneficial or detrimental compared to fixed mutation strategies.
The huge performance superiority of quantum computers for some specific problems lies in their direct use of quantum mechanical phenomena (e.g. superposition of states) to perform computations. This has motivated the creation of quantum-inspired evolutionary algorithms (QIEAs), which successfully use some quantum physics principles to improve the performance of evolutionary algorithms (EAs) for classical computers. This paper proposes a novel QIEA (Quantum-Inspired Linear Genetic Programming - QILGP) for automatic synthesis of machine code (MC) programs and aims to present a preliminary evaluation of applying the quantum-inspiration paradigm to evolve programs by using two symbolic regression problems. QILGP performance is compared with AIMGP model, since it is the most successful genetic programming technique to evolve MC. On first problem, the hit ratio of QILGP (100%) is greater than the one of AIMGP (77%). On second problem, QILGP seems to carry on a less greedy search than AIMGP. Since QILGP presents some satisfactory results, this paper shows that the quantum-inspiration paradigm can be a competitive approach to evolve programs more efficiently, which encourages further developments of that first and simplest QILGP model with multiple individuals.
We present a computational model of creative design based on collaborative interactive genetic algorithms. We test our model on floorplanning. We guide the evolution of floorplans based on subjective and objective criteria. The subjective criteria consists of designers picking the floorplan they like the best from a population of floorplans, and the objective criteria consists of coded architectural guidelines. We support collaboration by allowing individual designers to view each others' designs during the evolutionary process and the sharing of designs via case injection. This methodology supports team design, and reflects the view of creativity that collaboration accounts for much of our intelligence and creativity. We present a description of the model and a comparative study of floorplans created individually versus collaboratively. Our results show that floorplans created collaboratively were considered to be more "revolutionary" and "original" than those created individually.
As the size of CMOS devices is approaching the atomic level, the increasing intrinsic device variability is leading to higher failure rates in conventional CMOS designs. This paper introduces a design tool capable of evolving CMOS topologies using a modified form of Cartesian Genetic Programming and a multi-objective strategy. The effect of intrinsic variability within the design is then analysed using statistically enhanced SPICE models based on 3D-atomistic simulations. The goal is to produce industry-feasible topology designs which are more tolerant to the random fluctuations that will be prevalent in future technology nodes. The results show evolved XOR and XNOR CMOS topologies and compare the impact of threshold voltage variation on the evolved designs with those from a standard cell library.
We examine the problem to partition a square into convex polygons which are as circular as possible. Circular means that the polygon's aspect ratio is supposed to be near 1. The aspect ration of a convex polygon denotes the ratio of the diameters of the smallest circumscribing circle to the largest inscribed disk. This problem has been solved for the equilateral triangle as well as for regular k-gon with k > 4. In the case of a square, the optimal solution is still an open problem. We are planning to find a solution which is 'good enough' with the help of evolutionary algorithms.
VANETs are ad hoc networks in which devices are vehicles moving at high speeds. This kind of network is getting more and more importance since it has many practical and important applications, like multimedia file sharing (e.g., maps, music, news, weather), or dissemination of alarm messages (e.g., accidents, traffic jams, bad road conditions). One important problem faced in ad hoc networks is network partitioning, causing the formation of isolated clusters, and preventing devices in different clusters from communicating. Usually, devices composing the ad hoc network are provided with other communication interfaces rather than Wi-Fi and/or Bluetooth that allow them to connect to remote devices, such as GPRS/HSDPA. Additionally, there exists some network infrastructure in cities or roads that could be used by VANETs (e.g. hotspots). By taking advantage of these technologies and infrastructures, devices could be able to form a hybrid network, establishing remote links between them (called bypass links) in order to improve the network connectivity by joining, for example, separate clusters. In this work, we face the problem of optimizing the number and location of these remote connections for maximizing the QoS of the network. We use an efficient genetic algorithm with structured population, called cellular genetic algorithm (cGA), to optimize this hard problem. The evaluation of the quality of the network connectivity is made using small world properties. Our goal is to find highly accurate solutions (that could be used as reference values for future works) and then analyze the influence of the quality of the solutions in the real behavior of the network. This is achieved by using the JANE simulator to disseminate a message in the network using two broadcasting protocols having different features.
This paper studies the point correspondence prob- lem for which a diversity of qualitative and statistical solutions exist. Most of them use local optimizations between neighboring frames to determine trajectories for moving points. We present improved extensive algorithm using dynamic programming method which provides global optimum for functional based both on nearest neighbor and smooth motion models. We considered dynamic scenes with multiple, independently moving objects in which feature points may enter and leave the view field. Experiments with real and synthetic data over a wide range of scenarios and system parameters are presented to validate the claims about the performance of the proposed algorithm.
The basic framework of next generation intelligent transport systems (ITSs) is discussed. We propose a new congestion forecast system, which reacts to dynamically changing traffic conditions based on a coordination mechanism using pheromone communication models. We evaluate and verify the basic effectiveness of this method using simple simulations.
Supervised neural networks (NNs) have been successfully applied to solve classification problems. Various NN training algorithms were developed, including the particle swarm optimiser (PSO), which was proved to outperform the standard back propagation training algorithm on a selection of problems. It was, however, usually assumed that the decision boundaries do not change over time. Such assumption is often not valid for real life problems, and training algorithms have to be adapted to track the changing decision boundaries and detect new boundaries as they appear. Various dynamic versions of the PSO have already been developed, and this paper investigates the applicability of dynamic PSO to NN training in changing environments.
We investigate the properties of genetic algorithms (GAs) applied to fitness functions perturbed concurrently by additive and multiplicative noise that each take on finitely many values. First we explicitly construct a Markov chain that models GAs in this noisy environment. By analyzing this chain, we establish a condition that is both necessary and sufficient for GAs to eventually find a globally optimal solution with probability 1. Furthermore, we identify a condition that is both necessary and sufficient for GAs to eventually with probability 1 fail to find any globally optimal solution. Interestingly, both of these conditions are completely determined by the fitness function and multiplicative noise, and they are unaffected by the additive noise. Our analysis also shows that the chain converges to stationarity. Based on this property and the transition probabilities of the chain, we derive an upper bound for the number of iterations sufficient to ensure with certain probability that a GA selects a globally optimal solution upon termination.
In this paper we present a two-layered evolutionary system based on Voronoi regions to predict the initial return of a sample of initial pubic offerings. The proposed solution partitions the input space by evolving a set of prototypes using evolution strategies and subsequently fits specialized models to each of them. The exercise is repeated to produce a set of predictive models. The forecast for the return of new patterns is obtained averaging the solutions provided by different models into a single figure. The system is benchmarked against alternatives with the result of a strong relative performance.
Engine calibration, the tuning process of controller parameters in automotive engine development, can be formulated as a Multi-objective Optimization Problem (MOP) because it has various competing objectives. Experiment-Based Evolutionary Multi-objective Optimization is a promising approach for automatic engine calibration. In engine calibration, severe restrictions such as legislation of exhaust emissions appear as constraints on MOPs. Since the emission quantities observed by the instruments via experiments are used as the constraints, observation noise has to be considered. In this paper, we define this problem as 'Noisy constrained MOPs' and investigate the difficulties for Evolutionary Multi-objective Optimization (EMO). To overcome the difficulties, we introduce a constraint estimation approach. Moreover, a Pre-selection algorithm, an acceleration method for EMO, is employed to reduce the number of evaluations for expensive evaluation cost problems. The effectiveness of the proposed methods is demonstrated through numerical experiments.
Many linear structured genetic programming are proposed in the past years. Gene expression programming, as a classic linear represented genetic programming, is powerful in solving problems of data mining and knowledge discovery. Constrains of gene expression programming like head-tail mechanism do contribution to the legality of chromosome. However, they impair the flexibility and adaptability of chromosome to some extend. Inspired by the diversity of chromosome arrangements in biology, an unconstrained encoded gene expression programming is proposed to overcome above constraints. In this way, the search space is enlarged; meanwhile the parallelism and the adaptability are enhanced. A group of regression and classification experiments also show that unconstrained gene expression programming performs better than classic gene expression programming.
In this article, we have presented an unsupervised cancer classification technique based on multiobjective genetic fuzzy clustering of the tissue samples. In this regard, coordinate of the cluster centers have been encoded in the chromosomes and three fuzzy cluster validity indices are simultaneously optimized. Each solution of the resultant Pareto-optimal set has been boosted by a novel technique based on Support Vector Machine (SVM) classification. Finally, the clustering information possessed by the non-dominated solutions are combined through a majority voting ensemble technique to produce the final clustering solution. The performance of the proposed multiobjective clustering method has been compared to several other microarray clustering algorithms for three publicly available benchmark cancer data sets, viz., leukemia, Colon cancer and Lymphoma data to establish its superiority.
Several multi-objective evolutionary algorithms compare the hypervolumes of different sets of points during their operation, usually for selection or archiving purposes. The basic requirement is to choose a subset of a front such that the hypervolume of that subset is maximised. We describe a technique that improves the performance of hypervolume contribution based front selection schemes. This technique improves performance by allowing the update of hypervolume contributions after the addition or removal of a point, where these contributions would previously require full recalculation. Empirical evidence shows that this technique reduces runtime by up to 99% when compared to the cost of full contribution recalculation.
Because of constantly improving technologies, the complexity of Integrated Circuits is continuously increasing. Consequently chip-design becomes more and more challenging. Therefore an approach that allows a fast and efficient ASIC design is needed. Especially the organization of Chip-Design projects exhibits a very high complexity. Different tools can be used to execute the same task, resulting in a huge number of different possible design flows. The number of valid flows is delimited by different constraints. Resources are limited and different types of design tasks require different types of resources. Precedences between design tasks have to be considered. Because of these characteristics we developed an approach that uses a genetic algorithm to analyse and improve the organization of ASIC design projects.
Many interesting problems in numerical optimization are hybrid optimal control problems. Hybrid optimal control (HOC) problems include both continuous-valued variables and categorical variables in the problem formulation. For the types of problems envisioned here the categorical variables will specify the structure or sequence of events that qualitatively describes the trajectory or mission. Continuous variables are used in the modeling of the continuous dynamics. In this work, the mission planning problem is of interest. The problem is qualitatively different from the typical interception of multiple targets as the discrete variables now represent events like impulses, coast and thrust arcs that change the structure of the problem. In addition, the number of events in the categorical sequence is not fixed. For the dynamical assembly of events required for the solution of the mission planning problem, a scheme that defines events as modules consisting of parameters and constraints is presented. The method assembles the respective events one next to the other in time according to the given mission structure. For the generation of the initial guess, two new methods were developed that approximate optimal low-thrust trajectories. The first method, based on genetic algorithms (GA), handles the rendezvous constraints explicitly using a conditional penalty function. The second method, Feasible Region Analysis (FRA), is based on GA and nonlinear programming (NLP), which allows taking advantage of the GA capabilities in finding a global optimum and NLP ability in handling constraints. A rendezvous problem with known solution is solved.
When performing predictive data mining, the use of ensembles is known to increase prediction accuracy, compared to single models. To obtain this higher accuracy, ensembles should be built from base classifiers that are both accurate and diverse. The question of how to balance these two properties in order to maximize ensemble accuracy is, however, far from solved and many different techniques for obtaining ensemble diversity exist. One such technique is bagging, where implicit diversity is introduced by training base classifiers on different subsets of available data instances, thus resulting in less accurate, but diverse base classifiers. In this paper, genetic programming is used as an alternative method to obtain implicit diversity in ensembles by evolving accurate, but different base classifiers in the form of decision trees, thus exploiting the inherent inconsistency of genetic programming. The experiments show that the GP approach outperforms standard bagging of decision trees, obtaining significantly higher ensemble accuracy over 25 UCI datasets. This superior performance stems from base classifiers having both higher average accuracy and more diversity. Implicitly introducing diversity using GP thus works very well, since evolved base classifiers tend to be highly accurate and diverse.
This work introduces a hybrid between an elitist multi-objective evolutionary algorithm and a gradient-based descent method, which is applied only to certain (selected) solutions. Our proposed approach requires a low number of objective function evaluations to converge to a few points in the Pareto front. Then, the rest of the Pareto front is reconstructed using a method based on rough set theory, which also requires a low number of objective function evaluations. Emphasis is placed on the effectiveness of our proposed hybrid approach when increasing the number of decision variables, and a study of the scalability of our approach is also presented.
Evolutionary Algorithms based on Probabilistic Modeling is a growing research field. Recently, hybrids that borrow ideas from the field of classification were introduced. We extend such hybrids, and evaluate four strategies for truncation of an over-sized population of samples. The strategies are evaluated over a number of difficult problems from the literature, among them, a hierarchical 256-bit HIFF problem. We show that over-sampling in conjunction with a truncation strategy can guide the search without increasing the number of performed fitness evaluations per generation, and that a truncation strategy which inverses the sampling pressure can, fitness-wise, perform significantly better than regular sampling.
Large scale global optimization (LSGO) is a very important and extremely difficult task in optimization domain, which is urgently needed for scientific and engineering applications. Recently, decompose-and-conquer strategy has become a promising method to handle LSGO problems. In this paper, we propose a new strategy variance priority (VP) to improve the classical cooperative co-evolution framework. Based on this proposed strategy, a new LSGO algorithm, variance priority based cooperative co-evolution differential evolution (VP-DECC), is developed. The advantages of VP strategy over the other decompose-and-conquer strategies are experimentally investigated. Especially, it has shown excellent performance in dealing with more complex problems.
Difference evolution (DE) has shown its effectiveness in solving many problems. The difference vector (DV), which serves as a measure for the dispersion of candidate solutions, has a key role in the adaptive mutation of DE. Traditionally, DE adopts one DV. In this paper, we investigate the use of more than one DV and propose the Poisson differential evolution (PDE) with a varying number of DVs based on Poisson distribution. Experimental results on 24 numerical benchmark functions point out the ineffectiveness of increasing DVs in the original DE. Moreover, the results show that the proposed PDE can achieve significant improvement on DE in terms of solution quality and convergence speed, which validates the benefit of varying number of DVs for DE.
In this paper we report on the effect of viral infection with tropism on the formation of building blocks in genetic operations. In previous research, we applied genetic algorithms to the analysis of time-series signals with noise. We demonstrated the possibility of reducing the number of required entities and improving the rate of convergence when searching for a solution by having some of the host chromosomes harbor viruses with a tropism function. Here, we simulate problems having both multimodality and deceptiveness features and problems that include noise as test functions, and show that viral infection with tropism can increase the proportion of building blocks in the population when it cannot be assumed that a necessary and sufficient number of entities are available to find a solution. We show that this capability is especially noticeable in problems that include noise.
In this article we apply information visualization techniques to the domain of swarm intelligence. We describe an intuitive approach that enables researchers and designers of stochastic optimization algorithms to efficiently determine trends and identify optimal regions in an algorithm's parameter search space. The parameter space is evenly sampled using low-discrepancy sequences, and visualized using parallel coordinates. Various techniques are applied to iteratively highlight areas that influence the optimization algorithm's performance on a particular problem. By analyzing experimental data with this technique, we were able to gain important insight into the complexity of the target problem domain. For example, we were able to confirm some underlying theoretical assumptions of an important class of population-based stochastic algorithms. Most importantly, the technique improves the efficiency of finding good parameter settings by orders of magnitude.
Building blocks are solutions to sub-parts of a problem which can help in the formation of good solutions to the whole problem. Building blocks are widely recognised as important elements in the successful application of evolutionary algorithms (EAs), but there is as yet no general method by which the building blocks of a problem can be identified. We describe and evaluate a new system which creates a visual representation of these building blocks by displaying the possible gene values of a problem on a canvas, with the distance between the nodes representing two values determined by the number of individuals in the population which contain both values. Building blocks then appear as clusters of nodes, and they can be identified easily: moreover, the evolution of the building blocks as the EA proceeds can be tracked. This system will help in understanding the structure of problems and in tuning EAs to solve them well.
In this paper we discuss the notion of situated evolution. Our treatment includes positioning situated evolution on the map of evolutionary processes in terms of time- and space-embeddedness, and the identification of decentralization as an orthogonal property. We proceed with a selected overview of related literature in the categories of our interest. This overview enables us to distill further detailes that distinguish the encountered methods. As it turns out the essential differences can be captured through the mechanics of selection and fertilization. These insights are aggregated into a new model called the Situated Evolution Method, which is then used to provide a fine-grained map of exisiting work.
Despite the wide-spread popularity of estimation of distribution algorithms (EDAs), there has been no theoretical proof that there exist optimisation problems where EDAs perform significantly better than traditional evolutionary algorithms. Here, it is proved rigorously that on a problem called SubString, a simple EDA called univariate marginal distribution algorithm (UMDA) is efficient, whereas the (1+1) EA is highly inefficient. Such studies are essential in gaining insight into fundamental research issues, i.e., what problem characteristics make an EDA or EA efficient, under what conditions an EDA is expected to outperform an EA, and what key factors are in an EDA that make it efficient or inefficient.
Metabolic P systems (MP systems) are a special class of P systems introduced for expressing biological metabolic phenomena. The graphical formalism of MP graphs represents, in a simple and intuitive way, the structure of these systems. However, there are some cases in which they would be better specified by semi-structured textual documents, especially for information exchanging between different computational tools elaborating on different biological aspects. The aim of this paper is to define such a way of exportation from MP graphs to XML documents. It turns out that all properties which guarantee the correctness of MP graphs can be formally described by means of logical formulae on trees, and completely expressed as XML constraints in XSD (XML Schema Definition), a W3C standard for XML validation.