Using Disruptive Selection to Maintain Diversity in Genetic Algorithms

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. A novel selection method, disruptive selection, has been proposed. This method adopts a nonmonotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional selection methods, this method favors both superior and inferior individuals. Since genetic algorithms allocate exponentially increasing numbers of trials to the observed better parts of the search space, it is difficult to maintain diversity in genetic algorithms. We show that Disruptive Genetic Algorithms (DGAs) effectively alleviate this problem by first demonstrating that DGAs can be used to solve a nonstationary search problem, where the goal is to track time-varying optima. Conventional Genetic Algorithms (CGAs) using proportional selection fare poorly on nonstationary search problems because of their lack of population diversity after convergence. Experimental results show that DGAs immediately track the optimum after the change of environment. We then describe a spike function that causes CGAs to miss the optimum. Experimental results show that DGAs outperform CGAs in resolving a spike function.     

Why DGAs work well on GA-hard functions?

What makes a problem easy or hard for a genetic algorithm (GA)? Much previous work has studied this question by applying Walsh analysis.⁴⁾ In this paper, we demonstrate a function that is GA-hard by analyzing the Walsh coefficients of this function’s Walsh decomposition. Then, we construct five functions with differing degrees of difficulty for genetic algorithms. Some are GA-easy and some are GA-hard. In a previous paper,²⁹⁾ wh have proposed a novel selection method,disruptive selection. This method devotes more trials to both better solutions and worse solutions than it does to moderate solutions, whereas the conventional method allocates its attention according to the performance of each solution. Experimental results show that DGAs (GAs using disruptive selection) perform very well on both GA-easy and GA-hard functions. Finally, we discuss why DGAs outperform conventional GAs.     

Genetic algorithms for video segmentation

The current paper presents a new genetic algorithm (GA)-based method for video segmentation. The proposed method is specifically designed to enhance the computational efficiency and quality of the segmentation results compared to standard GAs. The segmentation is performed by chromosomes that independently evolve using distributed genetic algorithms (DGAs). However, unlike conventional DGAs, the chromosomes are initiated using the segmentation results of the previous frame, instead of random values. Thereafter, only unstable chromosomes corresponding to moving object parts are evolved by crossover and mutation. As such, these mechanisms allow for effective solution space exploration and exploitation, thereby improving the performance of the proposed method in terms of speed and segmentation quality. These advantages were confirmed based on experiments where the proposed method was successfully applied to both synthetic and natural video sequences.     

解决旅行商问题的改进算法

首先提出旅行商问题(TSP),然后实现了常见的解决TSP问题的算法:有传统算法中的贪心算法和回溯法,还有现代优化算法中的基本遗传算法。并针对这3种算法的缺点提出了一种改进的算法,即综合运用贪心算法和遗传算法,依据贪心选择的原则指导遗传操作,可以大大加快搜索的速度,仿真实验表明改进的算法是十分有效和实用的。     

0-1背包问题及其算法分析

0-1背包问题是算法设计分析中的经典问题,本文主要通过对回溯法、动态规划、贪心算法和遗传算法的研究,分析这四种方法在求解0-1背包问题时的优缺点并进行了比较.     

Search Algorithms for Regression Test Case Prioritization

Regression testing is an expensive, but important, process. Unfortunately, there may be insufficient resources to allow for the reexecution of all test cases during regression testing. In this situation, test case prioritization techniques aim to improve the effectiveness of regression testing by ordering the test cases so that the most beneficial are executed first. Previous work on regression test case prioritization has focused on greedy algorithms. However, it is known that these algorithms may produce suboptimal results because they may construct results that denote only local minima within the search space. By contrast, metaheuristic and evolutionary search algorithms aim to avoid such problems. This paper presents results from an empirical study of the application of several greedy, metaheuristic, and evolutionary search algorithms to six programs, ranging from 374 to 11,148 lines of code for three choices of fitness metric. The paper addresses the problems of choice of fitness metric, characterization of landscape modality, and determination of the most suitable search technique to apply. The empirical results replicate previous results concerning greedy algorithms. They shed light on the nature of the regression testing search space, indicating that it is multimodal. The results also show that genetic algorithms perform well, although greedy approaches are surprisingly effective, given the multimodal nature of the landscape     

A problem reduction based approach to discrete optimization algorithm design

The paper presents a novel approach to formal algorithm design for a typical class of discrete optimization problems. Using a concise set of program calculation rules, our approach reduces a problem into subproblems with less complexity based on function decompositions, constructs the problem reduction graph that describes the recurrence relations between the problem and subproblems, from which a provably correct algorithm can be mechanically derived. Our approach covers a large variety of algorithms and bridges the relationship between conventional methods for designing efficient algorithms (including dynamic programming and greedy) and some effective methods for coping with intractability (including approximation and parameterization).     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

Using metaheuristic algorithms for parameter estimation in generalized Mallows models

This paper deals with the problem of parameter estimation in the generalized Mallows model (GMM) by using both local and global search metaheuristic (MH) algorithms. The task we undertake is to learn parameters for defining the GMM from a dataset of complete rankings/permutations. Several approaches can be found in the literature, some of which are based on greedy search and branch and bound search. The greedy approach has the disadvantage of usually becoming trapped in local optima, while the branch and bound approach, basically A^* search, usually comes down to approximate search because of memory requirements, losing in this way its guaranteed optimality. Here, we carry out a comparative study of several MH algorithms (iterated local search (ILS) methods, variable neighborhood search (VNS) methods, genetic algorithms (GAs) and estimation of distribution algorithms (EDAs)) and a tailored algorithm A^* to address parameter estimation in GMMs. We use 22 real datasets of different complexity, all but one of which were created by the authors by preprocessing real raw data. We provide a complete analysis of the experiments in terms of accuracy, number of iterations and CPU time requirements.     

基于生成对抗网络的恶意域名训练数据生成

当前僵尸网络大量采用DGA算法躲避检测,针对主流的基于人工规则的检测算法无法对最新产生的DGA域名进行识别检测和基于机器学习的检测算法缺乏演化的训练数据的问题,提出了一种基于Ascall编码方式定义域名编、解码器,并结合生成对抗网络构造域名字符生成器来预测生成DGA变体样本的方法。实验结果表明,在采用生成数据进行分类器训练和性能评估中,此方法生成的DGA域名变体样本可充当真实DGA样本,验证了生成数据的有效性并可用于DGA域名检测器的训练评估。     

Algorithmic Representations of Managerial Search Behavior

We use targeted behavioral experiments to test the extent to which greedy algorithms replicate search behavior. Many simulation models use greedy algorithms to represent a firm’s trial-and-error based exploration (i.e., backward-looking search). This implies that managers always reject changes that decrease performance relative to the status quo. Although we observe significant heterogeneity in backward-looking search behavior, over 50 % of our subjects deviate from greedy search behavior by occasionally preserving performance-decreasing changes. The likelihood of such preservation was inversely related to the magnitude of the performance decrease. While search behavior is likely context specific, our analysis suggests that non-greedy firm search cannot be dismissed outright. Substituting non-greedy algorithms for greedy ones will alter the behavior of some simulation models used in economic research. We recommend that future work in this area report whether key findings are dependent on the use of greedy or non-greedy search algorithms. We also suggest that researchers explicitly discuss which algorithm best represents backward-looking search in the phenomenon under study.     

Evolutionary decision-makings for the dynamic weapon-target assignment problem

The dynamic weapon-target assignment (DWTA) problem is an important issue in the field of military command and control. An asset-based DWTA optimization model was proposed with four kinds of constraints considered, including capability constraints, strategy constraints, resource constraints and engagement feasibility constraints. A general “virtual” representation of decisions was presented to facilitate the generation of feasible decisions. The representation is in essence the permutation of all assignment pairs. A construction procedure converts the permutations into real feasible decisions. In order to solve this problem, three evolutionary decision-making algorithms, including a genetic algorithm and two memetic algorithms, were developed. Experimental results show that the memetic algorithm based on greedy local search can generate obviously better DWTA decisions, especially for large-scale problems, than the genetic algorithm and the memetic algorithm based on steepest local search.     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

Evaluation of two heuristic approaches to solve the ontology meta-matching problem

Nowadays many techniques and tools are available for addressing the ontology matching problem, however, the complex nature of this problem causes existing solutions to be unsatisfactory. This work aims to shed some light on a more flexible way of matching ontologies. Ontology meta-matching, which is a set of techniques to configure optimum ontology matching functions. In this sense, we propose two approaches to automatically solve the ontology meta-matching problem. The first one is called maximum similarity measure, which is based on a greedy strategy to compute efficiently the parameters which configure a composite matching algorithm. The second approach is called genetics for ontology alignments and is based on a genetic algorithm which scales better for a large number of atomic matching algorithms in the composite algorithm and is able to optimize the results of the matching process.     

带度约束的最小直径应用层多播路由问题的启发式遗传算法

由于IP多播难以在因特网环境中配置,应用层多播作为IP多播的一种替代方案得到越来越多的研究。从网络设计的角度来看,应用层多播在网络代价模型及路由策略方面与传统的IP多播有很大区别。本文研究了带度约束的最小直径应用层网络多播路由问题,提出了解决该问题的启发式遗传算法。通过大量仿真实验,我们对比分析了两种贪婪算法法和遗传算法的性能。实验显示,启发式遗传算法具有较好的性能。     

多种群退火贪婪混合遗传算法

遗传算法是应用比较广泛的一种随机优化算法,遗传算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。为了提高遗传算法的性能,论文通过将局部搜索能力较强的贪婪算法引入遗传算法,并且同模拟退火和多种群并行遗传进化思想有机结合起来的方法,提出了一个改进型的算法——多种群退火贪婪混合遗传算法(MultigroupAnnealingGreedyHybridGeneticAlgorithm,简称MAGHGA)。仿真结果表明,该算法避免了在遗传算法中存在的早熟收敛问题,增强了算法的全局收敛性,同时也有效地提高了算法的收敛速度。     

移动传感器网络中路径扫描覆盖问题研究

扫描覆盖作为无线传感器网络中的重要应用之一,通过规划移动传感器对区域内兴趣点（POI）进行定期覆盖,因此相较于传统覆盖方法能以更低廉的成本监测POI。研究最少传感器数量-最小罚时路径扫描覆盖问题,即通过调度移动传感器扫描给定路径上的POI集合,使传感器使用数量及产生的POI总罚时成本之和最小。将该问题转换为整数规划,并基于该问题的特殊结构设计贪心算法和遗传算法,以求解大规模实例。在遗传算法基础上引入模拟退火操作,以设计一种遗传模拟退火算法,从而提高求解质量和算法局部寻优能力。实验结果表明,所提贪心算法、遗传算法及遗传模拟退火算法均有较好的收敛性,贪心算法求解质量相对较差,但求解速度快;遗传算法解的质量更好,但存在不稳定的问题,局部寻优能力较弱;遗传模拟退火算法的局部寻优能力和求解稳定性明显增强,解的质量优于其他两种算法。     

高校自动排课系统算法比较分析

课程表的编排是高校教务管理中最为重要和复杂的一项工作。通过对几种自动排课算法的合理比较。统筹分析出各自的优劣,得出贪婪算法的综合适用性是最优的结论。在此基础之上．进一步分析贪婪算法是如何逐步解决排课的现实问题,并给出基于贪婪算法的自动排课系统算法的具体实现过程。     

二重结构编码遗传算法及其在贷款组合优化决策中的应用

对于综合考虑贷款收益和风险的贷款组合配给决策模型 ,算法上是一类背包问题 ,但它有其特殊性 .采用二重结构编码的遗传算法 ,结合贪心算法和局部搜索算法 ,可以提高这类问题求解的效率 ,并在运算时间和解的精度上取得较好的平衡 .