Forking genetic algorithms: GAs with search space division schemes

In this article, we propose a new type of genetic algorithm (GA), the forking GA (fGA), which divides the whole search space into subspaces, depending on the convergence status of the population and the solutions obtained so far. The fGA is intended to deal with multimodal problems that are difficult to solve using conventional GAs. We use a multipopulation scheme that includes one parent population that explores one subspace and one or more child populations exploiting the other subspace. We consider two types of fGAs, depending on the method used to divide the search space. One is the genotypic fGA (g-fGA), which defines the search subspace for each subpopulation, depending on the salient schema within the genotypic search space. The other is the phenotypic fGA (p-fGA), which defines a search subspace by a neighborhood hypercube around the current best individual in the phenotypic feature space. Empirical results on complex function optimization problems show that both the g-fGA and p-fGA perform well compared to conventional GAs. Two additional utilities of the p-fGA are also studied briefly.     

一种新的求解动态连续优化的分层粒子群算法

为了高效求解动态连续优化问题,提出一种分层粒子群优化算法。该算法将动态函数定义域分成Q个子空间,每个空间用一个粒子群作为第一层进行独立搜索,Q个子空间的最优粒子再组成一个全局粒子群进行全局搜索,以达到全局牵引的作用,同时提出探测环境和响应环境的策略。利用经典的动态函数对算法进行测试,结果表明所提出算法能够迅速适应环境变化和跟踪最优解的变化,效果令人满意。     

Designing fuzzy logic controllers using a multiresolutional searchparadigm

A multiresolutional search paradigm is employed to design optimal fuzzy logic controllers in a variable structure simulation environment. The initial search space is evaluated with a coarse resolution and some of the subspaces are selected as candidate regions for global optimum. New optimization processes are then created to investigate the candidate search spaces in detail, a process which continues until a solution is found. This search paradigm was implemented using hierarchical distributed genetic algorithms (HDGAs)-search agents solving different degrees of abstracted problems. Creation/destruction of agents is executed dynamically during the operation based on their performance. In the application to fuzzy systems, the HDGA investigates design alternatives such as different types of membership functions and the number of the fuzzy labels, as well as their optimal parameter settings, all at the same time. This paradigm is demonstrated with an application to the design of a fuzzy controller for an inverted pendulum     

基于K-均值聚类的协同进化粒子群优化算法

针对粒子群优化（PSO）算法优化高维问题时,易陷入局部最优,提出一种基于K-均值聚类的协同进化粒子群优化（KMS-CCPSO）算法。该算法通过引入K-均值算法扩大种群的局部搜索范围,采用柯西分布和高斯分布相结合的方法更新粒子的位置。实验结果表明,该算法具有较好的优化性能,其优势在处理高维问题上更为明显。     

限定GA搜索空间的WSF求解算法

波达方向（DOA）估计在无线传感器网络中得到了广泛的应用,本文针对DOA中加权子空间拟合（WSF）算法多维非线性优化计算量大的问题,提出一种限定遗传搜索空间的WSF求解算法.该方法将旋转不变子空间（ESPRIT）与无偏估计量的理论最小误差（TME）相结合来限定遗传算法的搜索空间,通过缩短遗传算法的基因长度来降低加权子空间拟合算法的求解复杂度.仿真结果表明,该算法的估计性能与WSF基本相同,与其它的一些智能优化算法相比,显著的降低了算法的计算量.     

融合分区和局部搜索的多模态多目标优化

为解决多模态多目标优化中种群多样性维持难和所得等价解数量不足问题,基于分区搜索和局部搜索,本研究提出一种融合分区和局部搜索的多模态多目标粒子群算法(multimodal multi-objective particle swarm optimization combing zoning search and local search,ZLS-SMPSO-MM)。在所提算法中,整个搜索空间被分割成多个子空间以维持种群多样性和降低搜索难度;然后,使用已有的自组织多模态多目标粒子群算法在每个子空间搜索等价解和挖掘邻域信息,并利用局部搜索能力较强的协方差矩阵自适应算法对有潜力的区域进行精细搜索。通过14个多模态多目标优化问题测试,并与其他5种知名算法进行比较;实验结果表明ZLS-SMPSO-MM在决策空间能够找到更多的等价解,且整体性能要好于所比较算法。     

遗传算法优化框架中使用嵌入的混合可视化和数据分析的过程设计优化

非线性、非凸、不连续的数学模型的使用,使得过程优化问题难以求解。虽然确定性方法已经取得了重大的进步,但随机方法,特别是遗传算法提供了一种更有优势的方法。然而,遗传算法的性质决定了其不适合求解带有高约束的问题。本文提出了一个适用于高度约束问题的目标遗传算法,算法中的算子：交叉和变异,是在数据分析步骤得到的关于可行区域和目标函数行为信息的基础上定义。数据分析是以平行坐标系中的可视化描述为基础,一种模式匹配算法,扫描园算法,通过学习向量量化的使用被扩展来自动地确定目标函数和搜索空间的关键特征,这些特征被用于确定遗传算子。对石油稳定问题应用新的目标遗传算法,其结果证明了方法的有用、高效和健壮性。作为数据分析的核心,可视化技术的使用也可以用于解释优化过程得到的结果。     

支持演化规则引擎的Rete算法研究

在演化规则模式匹配过程中, 存在内存空间有限与用户请求响应要求快速等问题, 传统的Rete算法并不能完全适合此类实际应用。针对此类问题, 在经典Rete算法的基础上, 通过从算法空间复杂度的角度对Rete网络结构匹配效率进行分析, 并结合系统动态演化过程中强动态和高实时性的特点, 引入节点复用技术构造Rete网络, 且以规则权重、入网时间为依据, 增设了Rete网络节点存储空间可调整机制, 完成了Rete算法在内存消耗与调节、匹配耗时方面的优化。对比测试表明, 优化后的算法提高了网络匹配性能, 实现了系统的平稳安全运行, 解决了演化系统模式匹配过程中存在的问题。     

基于目标空间划分的自适应多目标进化算法

目前,多目标进化算法在众多领域具有极高的应用价值,是优化领域的研究热点之一.分析已有多目标进化算法在保持种群多样性方面的不足并提出一种基于解空间划分的自适应多目标进化算法（space division basedadaptive multiobjective evolutionary algorithm,简称SDA-MOEA）来解决多目标优化问题.该方法首先将多目标优化问题的解空间划分为大量子空间,在算法进化过程中,每个子空间都保留一个非支配解集,以保证种群的多样性.另外,该方法根据每个子空间推进种群前进的距离,自适应地为每个子空间分配进化机会,以提高种群的进化速度.最后,利用3组共14个多目标优化问题检验SDA-MOEA的性能,并将SDA-MOEA与其他5个已有多目标进化算法进行对比分析.实验结果表明：在10个问题上,算法SDA-MOEA显著优于其他对比算法.     

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

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

Hierarchical contour matching for dental X-ray radiographs

The goal of forensic dentistry is to identify individuals based on their dental characteristics. In this paper we present a new algorithm for human identification from dental X-ray images. The algorithm is based on matching teeth contours using hierarchical chamfer distance. The algorithm applies a hierarchical contour matching algorithm using multi-resolution representation of the teeth. Given a dental record, usually a postmortem (PM) radiograph, first, the radiograph is segmented and a multi-resolution representation is created for each PM tooth. Each tooth is matched with the archived antemortem (AM) teeth, which have the same tooth number, in the database using the hierarchical algorithm starting from the lowest resolution level. At each resolution level, the AM teeth are arranged in an ascending order according to a matching distance and 50% of the AM teeth with the largest distances are discarded and the remaining AM teeth are marked as possible candidates and the matching process proceeds to the following (higher) resolution level. After matching all the teeth in the PM image, voting is used to obtain a list of best matches for the PM query image based upon the matching results of the individual teeth. Analysis of the time complexity of the proposed algorithm prove that the hierarchical matching significantly reduces the search space and consequently the retrieval time is reduced. The experimental results on a database of 187 AM images show that the algorithm is robust for identifying individuals based on their dental radiographs.     

On the robustness of population-based versus point-basedoptimization in the presence of noise

Practical optimization problems often require the evaluation of solutions through experimentation, stochastic simulation, sampling, or even interaction with the user. Thus, most practical problems involve noise. We address the robustness of population-based versus point-based optimization on a range of parameter optimization problems when noise is added to the deterministic objective function values. Population-based optimization is realized by a genetic algorithm and an evolution strategy. Point-based optimization is implemented as the classical Hooke-Jeeves pattern search strategy and threshold accepting as a modern local search technique. We investigate the performance of these optimization methods for varying levels of additive normally distributed fitness-independent noise and different sample sizes for evaluating individual solutions. Our results strongly favour population-based optimization, and the evolution strategy in particular     

一种基于佳点集原理的约束优化进化算法

提出一种基于佳点集理论解决约束优化问题的进化算法.它将实分圆域中均匀分布的佳点映射到求解问题的搜索空间,使得所构造的个体能在搜索空间内分布比采用随机方式更加均匀,并引进预交叉机制来平衡佳点取点个数与算法搜索能力之间的矛盾.新算法的遗传算子基于佳点技术构造,精度不受空间维数的限制,有利于高维优化问题.对6个标准测试函数的数值实验结果验证了新算法的通用性、有效性和稳健性.     

Vaccine-Enhanced Artificial Immune System for Multimodal Function Optimization

This paper emulates a biological notion in vaccines to promote exploration in the search space for solving multimodal function optimization problems using artificial immune systems (AISs). In this method, we first divide the decision space into equal subspaces. The vaccine is then randomly extracted from each subspace. A few of these vaccines, in the form of weakened antigens, are then injected into the algorithm to enhance the exploration of global and local optima. The goal of this process is to lead the antibodies to unexplored areas. Using this biologically motivated notion, we design the vaccine-enhanced AIS for multimodal function optimization, achieving promising performance.      

A novel multiobjective optimization algorithm based on bacterial chemotaxis

In this article a novel algorithm based on the chemotaxis process of Echerichia coli is developed to solve multiobjective optimization problems. The algorithm uses fast nondominated sorting procedure, communication between the colony members and a simple chemotactical strategy to change the bacterial positions in order to explore the search space to find several optimal solutions. The proposed algorithm is validated using 11 benchmark problems and implementing three different performance measures to compare its performance with the NSGA-II genetic algorithm and with the particle swarm-based algorithm NSPSO.     

A genetic algorithm-based search space splitting pattern and its application in hydraulic and coastal engineering problems

This article reports a search space splitting pattern that can be applied to genetic algorithms in order to ensure that the entire search space is investigated. Hence, by keeping the genetic algorithm simple, in a reasonable time and with a high degree of accuracy, the initial solutions can be improved toward the global optimum point. The simplicity of the presented method is an advantage that makes it useful for applied hydraulic and coastal engineering problems. The performance of the proposed method was evaluated by a benchmark optimization problem, Levy No. 5, and three hydraulic and coastal engineering problems: inverse problem of Manning’s equation, the equation of equilibrium beach profiles, and the settling velocity equation of natural sediment particles. The results indicated that the nonlinear complex problems can be solved by the proposed method with a high degree of accuracy. The proposed genetic algorithm-based search space splitting pattern can either be used exclusively or alternatively it can be combined with improved operators in the literature.

     

A Case-Based Micro Interactive Genetic Algorithm (CBMIGA) for interactive learning and search: Methodology and application to groundwater monitoring design

Interactive optimization algorithms use real–time interaction to include decision maker preferences based on the subjective quality of evolving solutions. In water resources management problems where numerous qualitative criteria exist, use of such interactive optimization methods can facilitate in the search for comprehensive and meaningful solutions for the decision maker. The decision makers using such a system are, however, likely to go through their own learning process as they view new solutions and gain knowledge about the design space. This leads to temporal changes (nonstationarity) in their preferences that can impair the performance of interactive optimization algorithms. This paper proposes a new interactive optimization algorithm – Case-Based Micro Interactive Genetic Algorithm – that uses a case-based memory and case-based reasoning to manage the effects of nonstationarity in decision maker’s preferences within the search process without impairing the performance of the search algorithm. This paper focuses on exploring the advantages of such an approach within the domain of groundwater monitoring design, though it is applicable to many other problems. The methodology is tested under non-stationary preference conditions using simulated and real human decision makers, and it is also compared with a non-interactive genetic algorithm and a previous version of the interactive genetic algorithm.     

改进GA的直流锅炉主汽温控制器参数优化研究

针对直流锅炉主汽温控制存在的大惯性、大延迟、时变性等问题,提出了带遗传算法(GA)优化的PID串级控制方法。采用了控制器分级多目标优化的改进方法,并利用遗传算法对串级PID参数进行实时动态优化,以适应主汽温对象的时变特性。针对基本的遗传算法进行改进,从而改善其运算量大且易早熟的缺点,提出了排序选择、自适应交叉和变异概率、压缩搜索空间等多种改进方法。仿真实验表明,所提出的方法能很好地改善系统的控制性能,有效提高控制系统的鲁棒性。     

Parameter optimization of distributed hydrological model with a modified dynamically dimensioned search algorithm

A modified version of the dynamically dimensioned search (MDDS) is introduced for automatic calibration of watershed simulation models. The distinguishing feature of the MDDS is that the algorithm makes full use of sensitivity information in the optimization procedure. The Latin hypercube one-factor-at-a-time (LH-OAT) technique is used to calculate the sensitivity information of every parameter in the model. The performance of the MDDS is compared to that of the dynamically dimensioned search (DDS), the DDS identifying only the most sensitive parameters, and the shuffled complex evolution (SCE) method, respectively, for calibration of the easy distributed hydrological model (EasyDHM). The comparisons range from 500 to 5000 model evaluations per optimization trial. The results show the following: the MDDS algorithm outperforms the DDS algorithm, the DDS algorithm identifying the most sensitive parameters, and the SCE algorithm within a specified maximum number of function evaluations (fewer than 5000); the MDDS algorithm shows robustness compared with the DDS algorithm when the maximum number of model evaluations is less than 2500; the advantages of the MDDS algorithm are more obvious for a high-dimensional distributed hydrological model, such as the EasyDHM model; and the optimization results from the MDDS algorithm are not very sensitive to either the variance (between 0.3 and 1) for randn′ used in the MDDS algorithm or the number of strata used in the Latin hypercube (LH) sampling.     

An improved artificial bee colony algorithm based on the strategy of global reconnaissance

The artificial bee colony (ABC) algorithm is a recently introduced swarm intelligence optimization algorithm based on the foraging behavior of a honeybee colony. However, many problems are encountered in the ABC algorithm, such as premature convergence and low solution precision. Moreover, it can easily become stuck at local optima. The scout bees start to search for food sources randomly and then they share nectar information with other bees. Thus, this paper proposes a global reconnaissance foraging swarm optimization algorithm that mimics the intelligent foraging behavior of scouts in nature. First, under the new scouting search strategies, the scouts conduct global reconnaissance around the assigned subspace, which is effective to avoid premature convergence and local optima. Second, the scouts guide other bees to search in the neighborhood by applying heuristic information about global reconnaissance. The cooperation between the honeybees will contribute to the improvement of optimization performance and solution precision. Finally, the prediction and selection mechanism is adopted to further modify the search strategies of the employed bees and onlookers. Therefore, the search performance in the neighborhood of the local optimal solution is enhanced. The experimental results conducted on 52 typical test functions show that the proposed algorithm is more effective in avoiding premature convergence and improving solution precision compared with some other ABCs and several state-of-the-art algorithms. Moreover, this algorithm is suitable for optimizing high-dimensional space optimization problems, with very satisfactory outcomes.