A survey: hybrid evolutionary algorithms for cluster analysis

Clustering is a popular data analysis and data mining technique. It is the unsupervised classification of patterns into groups. Many algorithms for large data sets have been proposed in the literature using different techniques. However, conventional algorithms have some shortcomings such as slowness of the convergence, sensitive to initial value and preset classed in large scale data set etc. and they still require much investigation to improve performance and efficiency. Over the last decade, clustering with ant-based and swarm-based algorithms are emerging as an alternative to more traditional clustering techniques. Many complex optimization problems still exist, and it is often very difficult to obtain the desired result with one of these algorithms alone. Thus, robust and flexible techniques of optimization are needed to generate good results for clustering data. Some algorithms that imitate certain natural principles, known as evolutionary algorithms have been used in a wide variety of real-world applications. Recently, much research has been proposed using hybrid evolutionary algorithms to solve the clustering problem. This paper provides a survey of hybrid evolutionary algorithms for cluster analysis.     

Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms

The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality.     

Evolutionary algorithms for scheduling m-machine flow shop with lot streaming

This paper addresses the problem of making sequencing and scheduling decisions for n jobs–m-machines flow shops under lot sizing environment. Lot streaming (Lot sizing) is the process of creating sub lots to move the completed portion of a production sub lots to down stream machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. Evolutionary algorithms that belong to search heuristics find more applications in recent research. Genetic algorithm (GA) and hybrid genetic algorithm (HEA) also known as hybrid evolutionary algorithm fall under evolutionary heuristics. On this concern this paper proposes two evolutionary algorithms namely, GA and HEA to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and set-up time. The following two algorithms are used to evaluate the performance of the proposed GA and HEA: (i) Baker's algorithm (BA), an optimal solution procedure for two-machine flow shop problem with lot streaming and makespan objective criterion and (ii) simulated annealing algorithm (SA) for m-machine flow shop problem with lot streaming and makespan and total flow time criteria.     

Application Layer Scheduling in Cloud: Fundamentals,Review and Research Directions

The cloud computing paradigm facilitates a finite pool of on-demand virtualized resources on a pay-per-use basis. For large-scale heterogeneous distributed systems like a cloud, scheduling is an essential component of resource management at the application layer as well as at the virtualization layer in order to deliver the optimal Quality of Services (QoS). The cloud scheduling, in general, is an NP-hard problem due to large solution space, thus, it is difficult to find an optimal solution within a reasonable time. In application layer scheduling, the tasks are mapped to logical resources (i.e., virtual machines), aiming to optimize one or more QoS parameters, and conforming to several constraints. Various algorithms have been proposed in the literature for application layer scheduling, where each of them is based on some fundamental design techniques like simple heuristics, meta-heuristics, and most recently hybrid heuristics. Although ample literature survey exists for cloud scheduling algorithms, none of them present their study exclusively for the application layer. In this survey paper, we present a study on task scheduling algorithms used only at the application layer of the cloud. We classify our study according to various fundamental techniques used in designing such scheduling algorithms. One of the main features of our study is that it covers numerous application type e.g., a set of independent tasks, simple workflow, scientific workflow, and MapReduce jobs. We also provide a comparative analysis of existing algorithms on various parameters like makespan, cost, resource utilization, etc. In the end, research directions for future work have been provided.     

Minimizing total earliness and tardiness on a single machine using a hybrid heuristic

This paper focuses on scheduling jobs with different processing times and distinct due dates on a single machine with no inserted idle time as to minimize the sum of total earliness and tardiness. This scheduling problem is a very important and frequent industrial problem that is common to most just-in-time production environments. This NP hard scheduling problem is herein solved using a hybrid heuristic which combines local search heuristics (dispatching rules, hill climbing and simulated annealing) and an evolutionary algorithm based on genetic algorithms. The heuristic involves low and high, relay and teamwork hybridization. Computational results reflect the sizeable solution quality improvement induced by hybridization, and assess the impact of each type of hybridization on the efficiency of the hybrid heuristic.     

Automated discovery of local search heuristics for satisfiability testing

The development of successful metaheuristic algorithms such as local search for a difficult problem such as satisfiability testing (SAT) is a challenging task. We investigate an evolutionary approach to automating the discovery of new local search heuristics for SAT. We show that several well-known SAT local search algorithms such as Walksat and Novelty are composite heuristics that are derived from novel combinations of a set of building blocks. Based on this observation, we developed CLASS, a genetic programming system that uses a simple composition operator to automatically discover SAT local search heuristics. New heuristics discovered by CLASS are shown to be competitive with the best Walksat variants, including Novelty+. Evolutionary algorithms have previously been applied to directly evolve a solution for a particular SAT instance. We show that the heuristics discovered by CLASS are also competitive with these previous, direct evolutionary approaches for SAT. We also analyze the local search behavior of the learned heuristics using the depth, mobility, and coverage metrics proposed by Schuurmans and Southey.     

An informed genetic algorithm for the examination timetabling problem

This paper presents the results of a study conducted to investigate the use of genetic algorithms (GAs) as a means of inducing solutions to the examination timetabling problem (ETP). This study differs from previous efforts applying genetic algorithms to this domain in that firstly it takes a two-phased approach to the problem which focuses on producing timetables that meet the hard constraints during the first phase, while improvements are made to these timetables in the second phase so as to reduce the soft constraint costs. Secondly, domain specific knowledge in the form of heuristics is used to guide the evolutionary process. The system was tested on a set of 13 real-world problems, namely, the Carter benchmarks. The performance of the system on the benchmarks is comparable to that of other evolutionary techniques and in some cases the system was found to outperform these techniques. Furthermore, the quality of the examination timetables evolved is within range of the best results produced in the field.     

Genetic scheduling for parallel processor systems: comparativestudies and performance issues

Task scheduling is essential for the proper functioning of parallel processor systems. Scheduling of tasks onto networks of parallel processors is an interesting problem that is well-defined and documented in the literature. However, most of the available techniques are based on heuristics that solve certain instances of the scheduling problem very efficiently and in reasonable amounts of time. This paper investigates an alternative paradigm, based on genetic algorithms, to efficiently solve the scheduling problem without the need to apply any restricted assumptions that are problem-specific, such is the case when using heuristics. Genetic algorithms are powerful search techniques based on the principles of evolution and natural selection. The performance of the genetic approach will be compared to the well-known list scheduling heuristics. The conditions under which a genetic algorithm performs best will also be highlighted. This will be accompanied by a number of examples and case studies     

Hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification: Overview and progress report

Nowadays, a promising way to obtain hybrid metaheuristics concerns the combination of several search algorithms with strong specialization in intensification and/or diversification. The flexible architecture of evolutionary algorithms allows specialized models to be obtained with the aim of providing intensification and/or diversification. The outstanding role that is played by evolutionary algorithms at present justifies the choice of their specialist approaches as suitable ingredients to build hybrid metaheuristics.This paper focuses on hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification. We first give an overview of the existing research on this topic, describing several instances grouped into three categories that were identified after reviewing specialized literature. Then, with the aim of complementing the overview and providing additional results and insights on this line of research, we present an instance that consists of an iterated local search algorithm with an evolutionary perturbation technique. The benefits of the proposal in comparison to other iterated local search algorithms proposed in the literature to deal with binary optimization problems are experimentally shown. The good performance of the reviewed approaches and the suitable results shown by our instance allow an important conclusion to be achieved: the use of evolutionary algorithms specializing in intensification and diversification for building hybrid metaheuristics becomes a prospective line of research for obtaining effective search algorithms.     

Automatic clustering algorithm based on multi-objective Immunized PSO to classify actions of 3D human models

Multi-objective clustering algorithms are preferred over its conventional single objective counterparts as they incorporate additional knowledge on properties of data in the from of objectives to extract the underlying clusters present in many datasets. Researchers have recently proposed some standardized multi-objective evolutionary clustering algorithms based on genetic operations, particle swarm optimization, clonal selection principles, differential evolution and simulated annealing, etc. In many cases it is observed that hybrid evolutionary algorithms provide improved performance compared to that of individual algorithm. In this paper an automatic clustering algorithm MOIMPSO (Multi-objective Immunized Particle Swarm Optimization) is proposed, which is based on a recently developed hybrid evolutionary algorithm Immunized PSO. The proposed algorithm provides suitable Pareto optimal archive for unsupervised problems by automatically evolving the cluster centers and simultaneously optimizing two objective functions. In addition the algorithm provides a single best solution from the Pareto optimal archive which mostly satisfy the users' requirement. Rigorous simulation studies on 11 benchmark datasets demonstrate the superior performance of the proposed algorithm compared to that of the standardized automatic clustering algorithms such as MOCK, MOPSO and MOCLONAL. An interesting application of the proposed algorithm has also been demonstrated to classify the normal and aggressive actions of 3D human models.     

Parallel LAN/WAN heuristics for optimization

We present in this work a wide spectrum of results on analyzing the behavior of parallel heuristics (both pure and hybrid) for solving optimization problems. We focus on several evolutionary algorithms as well as on simulated annealing. Our goal is to offer a first study on the possible changes in the search mechanics that the algorithms suffer when shifting from a LAN network to a WAN environment. We will address six optimization tasks of considerable complexity. The results show that, despite their expected slower execution time, the WAN versions of our algorithms consistently solve the problems. We report also some interesting results in which WAN algorithms outperform LAN ones. Those results are further extended to analyze the behavior of the heuristics in WAN with a larger number of processors and different connectivities.     

Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art

This paper provides a comprehensive survey of the most popular constraint-handling techniques currently used with evolutionary algorithms. We review approaches that go from simple variations of a penalty function, to others, more sophisticated, that are biologically inspired on emulations of the immune system, culture or ant colonies. Besides describing briefly each of these approaches (or groups of techniques), we provide some criticism regarding their highlights and drawbacks. A small comparative study is also conducted, in order to assess the performance of several penalty-based approaches with respect to a dominance-based technique proposed by the author, and with respect to some mathematical programming approaches. Finally, we provide some guidelines regarding how to select the most appropriate constraint-handling technique for a certain application, and we conclude with some of the most promising paths of future research in this area.     

Flow-shop sequencing using hybrid simulated annealing

Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.     

A tutorial survey of job-shop scheduling problems using genetic algorithms-I. representation

Job-shop scheduling problem (abbreviated to JSP) is one of the well-known hardest combinatorial optimization problems. During the last three decades, the problem has captured the interest of a significant number of researchers and a lot of literature has been published, but no efficient solution algorithm has been found yet for solving it to optimality in polynomial time. This has led to recent interest in using genetic algorithms (GAs) to address it. The purpose of this paper and its companion (Part II: Hybrid Genetic Search Strategies) is to give a tutorial survey of recent works on solving classical JSP using genetic algorithms. In Part I, we devote our attention to the representation schemes proposed for JSP. In Part II, we will discuss various hybrid approaches of genetic algorithms and conventional heuristics. The research works on GA/JSP provide very rich experiences for the constrained combinatorial optimization problems. All of the techniques developed for JSP may be useful for other scheduling problems in modern flexible manufacturing systems and other combinatorial optimization problems.     

An evolutionary algorithm for robust regression

A drawback of robust statistical techniques is the increased computational effort often needed as compared to non-robust methods. Particularly, robust estimators possessing the exact fit property are NP-hard to compute. This means that—under the widely believed assumption that the computational complexity classes NP and P are not equal—there is no hope to compute exact solutions for large high dimensional data sets. To tackle this problem, search heuristics are used to compute NP-hard estimators in high dimensions. A new evolutionary algorithm that is applicable to different robust estimators is presented. Further, variants of this evolutionary algorithm for selected estimators—most prominently least trimmed squares and least median of squares—are introduced and shown to outperform existing popular search heuristics in difficult data situations. The results increase the applicability of robust methods and underline the usefulness of evolutionary algorithms for computational statistics.     

PITAGORAS-PSP: Including domain knowledge in a multi-objective approach for protein structure prediction

Whenever evolutionary algorithms are used to solve certain classes of problems such as those that present a huge search space, the incorporation of problem-specific knowledge is required to achieve adequate levels of performance. In this paper, we propose a multi-objective optimization-based procedure that includes such a domain-specific knowledge to cope with a difficult problem, the protein structure prediction (PSP). This problem is considered to be an open problem as there is no recognized “best” procedure to find solutions. It presents a vast search space and the analysis of each protein conformation requires significant amount of computing time. In our procedure, we provide a reduction of the search space by using the dependent rotamer library and include new heuristics to improve a multi-objective approach to PSP based on the PAES algorithm. As it is shown in the paper, by using benchmark proteins from the CASP8 set, this hybrid PSP procedure provides competitive results when it is compared with some of the better proposals appeared up to now.     

Evolutionary algorithms for the satisfiability problem

Several evolutionary algorithms have been proposed for the satisfiability problem. We review the solution representations suggested in literature and choose the most promising one - the bit string representation - for further evaluation. An empirical comparison on commonly used benchmarks is presented for the most successful evolutionary algorithms and for WSAT, a prominent local search algorithm for the satisfiability problem. The key features of successful evolutionary algorithms are identified, thereby providing useful methodological guidelines for designing new heuristics. Our results indicate that evolutionary algorithms are competitive to WSAT.     

A review of clonal selection algorithm and its applications

Recently, clonal selection theory in the immune system has received the attention of researchers and given them inspiration to create algorithms that evolve candidate solutions by means of selection, cloning, and mutation procedures. Moreover, diversity in the population is enabled by means of the receptor editing process. The Clonal Selection Algorithm (CSA) in its canonical form and its various versions are used to solve different types of problems and are reported to perform better compared with other heuristics (i.e., genetic algorithms, neural networks, etc.) in some cases, such as function optimization and pattern recognition. Although the studies related with CSA are increasingly popular, according to our best knowledge, there is no study summarizing the basic features of these algorithms, hybrid algorithms, and the application areas of these algorithms all in one paper. Therefore, this study aims to summarize the powerful characteristics and general review of CSA. In addition, CSA based hybrid algorithms are reviewed, and open research areas are discussed for further research.     

基于外点法的混合遗传算法求解约束优化问题

提出了一种求解约束优化问题的混合遗传算法。它不是传统的在适应值函数中加一个惩罚项，而是在初始种群、交叉运算和变异运算过程中，把违反约束条件的个体用外点法处理设计出新的实数编码遗传算法。数值实验证明，新算法性能优于现有其他进化算法，是通用性强、高效稳健的方法。该方法兼顾了遗传算法和外点法的优点，既有较快的收敛速度，又能以非常大的概率求得约束优化问题全局最优解。     

一种求解多目标优化问题的进化算法混合框架

为了提高多目标优化算法的求解性能,提出一种启发式的基于种群的全局搜索与局部搜索相结合的多目标进化算法混合框架.该框架采用模块化、系统化的设计思想,不同模块可以采用不同策略构成不同的算法.采用经典的改进非支配排序遗传算法(NSGA-II)和基于分解的多目标进化算法(MOEA/D)作为进化算法的模块算法来验证所提混合框架的有效性.数值实验表明,所提混合框架具有良好性能,可以兼顾算法求解的多样性和收敛性,有效提升现有多目标进化算法的求解性能.