求解非线性方程组系统的改进差分进化算法

针对基于邻域拥挤的差分进化算法求解非线性方程组系统时存在丢根、陷入局部最优等不足,提出一种改进的差分进化算法.首先,提出一种个体预判机制,判断当前群体的个体属于哪一类,并分别采取不同的操作;其次,设计一种新的混合差分变异算子,以增强算法跳出局部最优的能力;然后,改进外部存档策略,延长了父代优秀个体在种群的保存时间,有利于搜索该优秀个体附近的根.在所选测试函数集上的实验结果表明,所提出的算法能有效搜索到非线性方程组系统的多个根,并与当前5种算法进行对比,所提出算法在找根率和成功率上更具优越性.     

Backward-chaining evolutionary algorithms

Starting from some simple observations on a popular selection method in Evolutionary Algorithms (EAs)—tournament selection—we highlight a previously-unknown source of inefficiency. This leads us to rethink the order in which operations are performed within EAs, and to suggest an algorithm—the EA with efficient macro-selection—that avoids the inefficiencies associated with tournament selection. This algorithm has the same expected behaviour as the standard EA but yields considerable savings in terms of fitness evaluations. Since fitness evaluation typically dominates the resources needed to solve any non-trivial problem, these savings translate into a reduction in computer time. Noting the connection between the algorithm and rule-based systems, we then further modify the order of operations in the EA, effectively turning the evolutionary search into an inference process operating in backward-chaining mode. The resulting backward-chaining EA creates and evaluates individuals recursively, backward from the last generation to the first, using depth-first search and backtracking. It is even more powerful than the EA with efficient macro-selection in that it shares all its benefits, but it also provably finds fitter solutions sooner, i.e., it is a faster algorithm. These algorithms can be applied to any form of population based search, any representation, fitness function, crossover and mutation, provided they use tournament selection. We analyse their behaviour and benefits both theoretically, using Markov chain theory and space/time complexity analysis, and empirically, by performing a variety of experiments with standard and back-ward chaining versions of genetic algorithms and genetic programming.     

Evolutionary design of Evolutionary Algorithms

Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility (which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

A Fast Clustering Based Evolutionary Algorithm for Super-Large-Scale Sparse Multi-Objective Optimization

During the last three decades, evolutionary algorithms (EAs) have shown superiority in solving complex optimization problems, especially those with multiple objectives and non-differentiable landscapes. However, due to the stochastic search strategies, the performance of most EAs deteriorates drastically when handling a large number of decision variables. To tackle the curse of dimensionality, this work proposes an efficient EA for solving super-large-scale multi-objective optimization problems with sparse optimal solutions. The proposed algorithm estimates the sparse distribution of optimal solutions by optimizing a binary vector for each solution, and provides a fast clustering method to highly reduce the dimensionality of the search space. More importantly, all the operations related to the decision variables only contain several matrix calculations, which can be directly accelerated by GPUs. While existing EAs are capable of handling fewer than 10 000 real variables, the proposed algorithm is verified to be effective in handling 1 000 000 real variables. Furthermore, since the proposed algorithm handles the large number of variables via accelerated matrix calculations, its runtime can be reduced to less than 10% of the runtime of existing EAs.      

Variants of evolutionary learning for interactive image retrieval

We systematically compare four variants of evolutionary algorithms (EAs) for relevance feedback (RF) in image retrieval. We focus on the small sample size (SSS) performance, i.e., the requirement to learn the user’s information need based on a small – between 2 and 25 – number of positive and negative training images. Despite this being a fundamental requirement, none of the existing works dealing with EAs for RF in image retrieval addresses it. Common for the four variants is the hierarchical, region-based image similarity model, with region and feature weights as parameters. The difference between the variants is in the objective function of the EA used to adjust the model parameters. The objective functions include: (O-1) precision; (O-2) average rank; (O-3) ratio of within-class (i.e., positive images) and between-class (i.e., positive and negative images) scatter; and (O-4) combination of O-2 and O-3. We note that – unlike O-1 and O-2 – O-3 and O-4 are not used in any of the existing works dealing with EAs for RF. The four variants are evaluated on five test databases, containing 61,895 general-purpose images, in 619 semantic categories. Results of the evaluation reveal that variants with objective functions O-3 and O-4 consistently outperform those with O-1 and O-2. Furthermore, comparison with the representative of the existing RF methods shows that EAs are both effective and efficient approaches for SSS learning in region-based image retrieval.     

A memory efficient stochastic evolution based algorithm for the multi-objective shortest path problem

Multi-objective shortest path (MOSP) problem aims to find the shortest path between a pair of source and a destination nodes in a network. This paper presents a stochastic evolution (StocE) algorithm for solving the MOSP problem. The proposed algorithm is a single-solution-based evolutionary algorithm (EA) with an archive for storing several non-dominant solutions. The solution quality of the proposed algorithm is comparable to the established population-based EAs. In StocE, the solution replaces its bad characteristics as the generations evolve. In the proposed algorithm, different sub-paths are the characteristics of the solution. Using the proposed perturb operation, it eliminates the bad sub-paths from generation to generation. The experiments were conducted on huge real road networks. The proposed algorithm is comparable to well-known single-solution and population-based EAs. The single-solution-based EAs are memory efficient, whereas, the population-based EAs are known for their good solution quality. The performance measures were the solution quality, speed and memory consumption, assessed by the hypervolume (HV) metric, total number of evaluations and memory requirements in megabytes. The HV metric of the proposed algorithm is superior to that of the existing single-solution and population-based EAs. The memory requirements of the proposed algorithm is at least half than the EAs delivering similar solution quality. The proposed algorithms also executes more rapidly than the existing single-solution-based algorithms. The experimental results show that the proposed algorithm is suitable for solving MOSP problems in embedded systems.     

A population dynamics model to describe gene frequencies in evolutionary algorithms

The performance of evolutionary algorithms (EAs) may heavily depend severely on a suitable choice of parameters such as mutation and crossover rates. Several methods to adjust those parameters have been developed in order to enhance EA performance. For this purpose, it is important to understand the EA dynamics, i.e., to appreciate the behavior of the population. Hence, this paper presents a new model of population dynamics to describe and predict the diversity in any particular generation. The formulation is based on selecting the probability density function of each individual. The population dynamics proposed is modeled for a generational population. The model was tested in several case studies of different population sizes. The results suggest that the prediction error decreases as the population size increases.     

A new approach to estimating the expected first hitting time of evolutionary algorithms

Evolutionary algorithms (EA) have been shown to be very effective in solving practical problems, yet many important theoretical issues of them are not clear. The expected first hitting time is one of the most important theoretical issues of evolutionary algorithms, since it implies the average computational time complexity. In this paper, we establish a bridge between the expected first hitting time and another important theoretical issue, i.e., convergence rate. Through this bridge, we propose a new general approach to estimating the expected first hitting time. Using this approach, we analyze EAs with different configurations, including three mutation operators, with/without population, a recombination operator and a time variant mutation operator, on a hard problem. The results show that the proposed approach is helpful for analyzing a broad range of evolutionary algorithms. Moreover, we give an explanation of what makes a problem hard to EAs, and based on the recognition, we prove the hardness of a general problem.     

NSGA-II-Based Design Space Exploration for Energy and Throughput Aware Multicore Architectures

Multicore architectures are mainstream due to ever increasing demand of throughput by modern applications. However, the suboptimal utilization of available resources in these architectures may imply an inevitable energy overhead. This energy overhead can only be avoided if the multicore systems support reconfiguration of available resources as per application demand. To achieve the target objectives (i.e., Energy efficiency with Throughput maximization) in multicore systems, many decision variables need to be optimized or analyzed to find the better trade-off. Heuristic-based approaches are aimed to provide a good-enough solution instead of a lengthy exhaustive search. This paper presents an Evolutionary Algorithm (EA)-based approach, i.e., Nondominated Sorting Genetic Algorithm-II (NSGA-II). Three decision variables, i.e., number of cores, cache size and frequency are used to find best solution. The proposed approach is validated over a set of parallel benchmarks using a cycle accurate simulator. The results show a significant amount of energy saving along with minimal impact on the throughput of the system.     

Parameter control system of evolutionary algorithm that is aided by the entire search history

In solving problems with evolutionary algorithms (EAs), the performance of the EA will be affected by its properties. As the properties of EA depend on the parameter setting, users need to tune the parameters to optimize the performance on different problems. In the case that the user does not have any prior knowledge of the problem, parameter tuning is very difficult and time consuming. One needs to try different combinations of parameter values to find the best setting. To solve this problem, one way is to control the parameters during the EA run. This paper proposes a new adaptive parameter control system, called Parameter Control system using entire Search History (PCSH). It is a general add-on system which is not restricted to a specific class of EA. Users are only required to know the range of the parameters. It automatically adjusts the parameters of an EA according to the entire search history, in a parameter-less manner. To illustrate the performance of PCSH, it is applied to control the parameters of three common classes of EAs: (1) canonical Genetic Algorithm (GA), (2) Particle Swarm Optimization (PSO) and (3) Differential Evolution (DE). For GA, we show that PCSH can automatically control the crossover operator, crossover values (uniformly sampled from the range) and mutation operator. For DE, we show that PCSH can automatically control the crossover operator, crossover values and the differential amplification factor (uniformly sampled from the ranges). For PSO, we show that PCSH can automatically control the two learning factors and the inertia weight (uniformly sampled from the range). Moreover, no special provision is needed at the initialization. 34 benchmark functions are used to evaluate the performance comprehensively. The test results show that, in most of the benchmark functions, the performance of the test EAs are improved or similar after adopting PCSH. It shows that PCSH keeps or improves the performance of the test EAs while relieving the heavy burden of the algorithm designer on the setting of some parameters.     

演化算法求解TSP问题的最新进展

TSP是一个著名的NP-hard问题.对近期出现的一些新的求解TSP问题的演化算法进行了比较全面的综述.其中有一类算法属于郭涛算法及其相应的改进算法,能够得到比传统演化算法更好的解,还有一类采用了实数编码的染色体表示方式,对求解TSP问题的新的染色体表示方式进行了尝试,还有的属于并行演化算法,通过增加并行进程的方式能够在原有算法的基础上得到更好的解.在综述这些算法的同时,还对比了它们的求解能力.最终的目的是希望通过对上述算法的研究,得到更合理的算法,推动演化算法研究TSP问题的进程.     

Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem

Group scheduling problems have attracted much attention owing to their many practical applications. This work proposes a new bi-objective serial-batch group scheduling problem considering the constraints of sequence-dependent setup time, release time, and due time. It is originated from an important industrial process, i.e., wire rod and bar rolling process in steel production systems. Two objective functions, i.e., the number of late jobs and total setup time, are minimized. A mixed integer linear program is established to describe the problem. To obtain its Pareto solutions, we present a memetic algorithm that integrates a population-based nondominated sorting genetic algorithm II and two single-solution-based improvement methods, i.e., an insertion-based local search and an iterated greedy algorithm. The computational results on extensive industrial data with the scale of a one-week schedule show that the proposed algorithm has great performance in solving the concerned problem and outperforms its peers. Its high accuracy and efficiency imply its great potential to be applied to solve industrial-size group scheduling problems.      

A variable reduction strategy for evolutionary algorithms handling equality constraints

Efficient constraint handling techniques are of great significance when Evolutionary Algorithms (EAs) are applied to constrained optimization problems (COPs). Generally, when use EAs to deal with COPs, equality constraints are much harder to satisfy, compared with inequality constraints. In this study, we propose a strategy named equality constraint and variable reduction strategy (ECVRS) to reduce equality constraints as well as variables of COPs. Since equality constraints are always expressed by equations, ECVRS makes use of the variable relationships implied in such equality constraint equations. The essence of ECVRS is it makes some variables of a COP considered be represented and calculated by some other variables, thereby shrinking the search space and leading to efficiency improvement for EAs. Meanwhile, ECVRS eliminates the involved equality constraints that providing variable relationships, thus improves the feasibility of obtained solutions. ECVRS is tested on many benchmark problems. Computational results and comparative studies verify the effectiveness of the proposed ECVRS.     

Group Search Optimizer: An Optimization Algorithm Inspired by Animal Searching Behavior

Nature-inspired optimization algorithms, notably evolutionary algorithms (EAs), have been widely used to solve various scientific and engineering problems because of to their simplicity and flexibility. Here we report a novel optimization algorithm, group search optimizer (GSO), which is inspired by animal behavior, especially animal searching behavior. The framework is mainly based on the producer-scrounger model, which assumes that group members search either for ldquofindingrdquo (producer) or for ldquojoiningrdquo (scrounger) opportunities. Based on this framework, concepts from animal searching behavior, e.g., animal scanning mechanisms, are employed metaphorically to design optimum searching strategies for solving continuous optimization problems. When tested against benchmark functions, in low and high dimensions, the GSO algorithm has competitive performance to other EAs in terms of accuracy and convergence speed, especially on high-dimensional multimodal problems. The GSO algorithm is also applied to train artificial neural networks. The promising results on three real-world benchmark problems show the applicability of GSO for problem solving.     

A modified Intelligent Water Drops algorithm and its application to optimization problems

The Intelligent Water Drop (IWD) algorithm is a recent stochastic swarm-based method that is useful for solving combinatorial and function optimization problems. In this paper, we investigate the effectiveness of the selection method in the solution construction phase of the IWD algorithm. Instead of the fitness proportionate selection method in the original IWD algorithm, two ranking-based selection methods, namely linear ranking and exponential ranking, are proposed. Both ranking-based selection methods aim to solve the identified limitations of the fitness proportionate selection method as well as to enable the IWD algorithm to escape from local optima and ensure its search diversity. To evaluate the usefulness of the proposed ranking-based selection methods, a series of experiments pertaining to three combinatorial optimization problems, i.e., rough set feature subset selection, multiple knapsack and travelling salesman problems, is conducted. The results demonstrate that the exponential ranking selection method is able to preserve the search diversity, therefore improving the performance of the IWD algorithm.     

Rotated neighbor learning-based auto-configured evolutionary algorithm基于旋转邻域学习的自配置进化算法

More and more evolutionary operators have been integrated and manually configured together to solve wider range of problems. Considering the very limited progress made on the automatic configuration of evolutionary algorithms (EAs), a rotated neighbor learning-based auto-configured evolutionary algorithm (RNLACEA) is presented. In this framework, multiple EAs are combined as candidates and automatically screened for different scenarios with a rotated neighbor structure. According to a ranking record and a group of constraints, the algorithms can be better scheduled to improve the searching efficiency and accelerate the searching pace. Experimental studies based on 14 classical EAs and 22 typical benchmark problems demonstrate that RNLACEA outperforms other six representative auto-adaptive EAs and has high scalability and robustness in solving different kinds of numerical optimization problems.     

非均匀演化算法及其应用

提出一种基于非均匀变异的演化算法模型;基于随机过程理论分析了该算法的自适应性,用该算法求解了实际的“油层结垢”问题;基于随机优化领域经典的高维多峰测试函数,同已有的同类算法做了对比.实验结果表明：在没有引入任何额外参数和计算的前提下,该算法具有更好的收敛性和稳定性.     

一种改进的基于差分进化的多目标进化算法

近年来运用进化算法（EAs）解决多目标优化问题（Multi-objective Optimization Problems MOPs）引起了各国学者们的关注。作为一种基于种群的优化方法,EAs提供了一种在一次运行后得到一组优化的解的方法。差分进化（DE）算法是EA的一个分支,最开始是用来解决连续函数空间的问题。提出了一种改进的基于差分进化的多目标进化算法（CDE）,并且将它与另外两个经典的多目标进化算法（MOEAs）NSGA-II和SPEA2进行了对比实验。     

Assessment of a parallel evolutionary optimization approach for efficient management of coastal aquifers

This study presents a parallel evolutionary optimization approach to determine optimal management strategies of large-scale coastal groundwater problems. The population loops of evolutionary algorithms (EA) are parallelized using shared memory parallelism to address the high computational demands of such applications. This methodology is applied to solve the management problems in an aquifer system in Kish Island, Iran using a three-dimensional density-dependent groundwater numerical model. EAs of continuous ant colony optimization (CACO), particle swarm optimization, and genetic algorithm are utilized to solve the optimization problems. By implementing the parallelization strategy, a speedup ratio of up to 3.53 on an 8-core processor is achieved in comparison with serial model. Based on solution quality and computational time criteria, the CACO robustness is observed in comparison to other EAs. Moreover, the optimization solution of the case study for a scenario of sea-level-rise indicates that a reduction of 20% in groundwater extraction rate is mainly due to the land-surface inundation caused by sea-level rise.