Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

An innovative framework for designing genetic algorithm structures

Genetic Algorithms are popular optimization algorithms, often used to solve complex large scale optimization problems in many fields. Like other meta-heuristic algorithms, Genetic Algorithms can only provide a probabilistic guarantee of the global optimal solution. Having a Genetic Algorithm (GA) capable of finding the global optimal solution with high success probability is always desirable. In this article, an innovative framework for designing an effective GA structure that can enhance the GA's success probability of finding the global optimal solution is proposed. The GA designed with the proposed framework has three innovations. First, the GA is capable of restarting its search process, based on adaptive condition, to jump out of local optima, if being trapped, to enhance the GA's exploration. Second, the GA has a local solution generation module which is integrated in the GA loop to enhance the GA's exploitation. Third, a systematic method based on Taguchi Experimental Design is proposed to tune the GA parameter set to balance the exploration and exploitation to enhance the GA capability of finding the global optimal solution. Effectiveness of the proposed framework is validated in 20 large-scale case study problems in which the GA designed by the proposed framework always outperforms five other algorithms available in the global optimization literature.     

遗传算法求解多模态优化问题的动力性

多模态函数一般存在多个局部极值解, 局部极值解处适应值的大小很大程度上影响了它们被遗传算法搜索到的概率. 为了弄清楚这种影响机制, 通过分析基因池遗传算法的无限种群动力系统, 刻画了双峰函数局部极值解的适值差与系统不动点之间的解析关系, 进一步分析推广了理论结果的适用范围. 最后, 提出针对多模态优化问题的两阶段遗传算法, 给出了应用理论结果改善遗传搜索性能的范例, 实验结果表明该算法对多模态函数的搜索性能有明显改善, 从侧面证明了理论结果在实际应用中的正确性.     

Various hybrid methods based on genetic algorithm with fuzzy logic controller

In this paper we propose several efficient hybrid methods based on genetic algorithms and fuzzy logic. The proposed hybridization methods combine a rough search technique, a fuzzy logic controller, and a local search technique. The rough search technique is used to initialize the population of the genetic algorithm (GA), its strategy is to make large jumps in the search space in order to avoid being trapped in local optima. The fuzzy logic controller is applied to dynamically regulate the fine-tuning structure of the genetic algorithm parameters (crossover ratio and mutation ratio). The local search technique is applied to find a better solution in the convergence region after the GA loop or within the GA loop. Five algorithms including one plain GA and four hybrid GAs along with some conventional heuristics are applied to three complex optimization problems. The results are analyzed and the best hybrid algorithm is recommended.     

基于自适应Memetic算法的多目标复杂网络社区检测

针对提高复杂网络社区检测准确度问题, 提出了一种自适应Memetic算法的多目标社区检测算法。在全局搜索中利用Logistic函数来设置与全局优化相应的交叉概率和变异概率,并将多目标优化问题转化成同时最小优化Kernel K-Means和Ratio Cut这两个目标函数;在局部搜索中利用权重将两个目标函数合并成一个局部优化目标,并采用爬山搜索来寻找个体最优。在虚拟和真实网络实验平台下,与五个基于遗传算法的方法以及Fast Modularity算法相比,结果表明算法能有效提高社区检测准确度,具有更好的寻优效果。     

Self-adjusting the intensity of assortative mating in genetic algorithms

Mate selection plays a crucial role in both natural and artificial systems. While traditional Evolutionary Algorithms (EA) usually engage in random mating strategies, that is, mating chance is independent of genotypic or phenotypic distance between individuals, in natural systems non-random mating is common, which means that somehow this mechanism has been favored during the evolutionary process. In non-random mating, the individuals mate according to their parenthood or likeness. Previous studies indicate that negative assortative mating (AM)—also known as dissortative mating—, which is a specific type of non-random mating, may improve EAs performance by maintaining the genetic diversity of the population at a higher level during the search process. In this paper we present the Variable Dissortative Mating Genetic Algorithm (VDMGA). The algorithm holds a mechanism that varies the GA’s mating restrictions during the run by means of simple rule based on the number of chromosomes created in each generation and indirectly influenced by the genetic diversity of the population. We compare VDMGA not only with traditional Genetic Algorithms (GA) but also with two preceding non-random mating EAs: the CHC algorithm and the negative Assortative Mating Genetic Algorithm (nAMGA). We intend to study the effects of the different methods in the performance of GAs and verify the reliability of the proposed algorithm when facing an heterogeneous set of landscapes. In addition, we include the positive Assortative Mating Genetic Algorithm (pAMGA) in the experiments in order test both negative and positive AM mechanisms, and try to understand if and when negative AM (or DM) speeds up the search process or enables the GAs to escape local optima traps. For these purposes, an extensive set of optimization test problems was chosen to cover a variety of search landscapes with different characteristics. Our results confirm that negative AM is effective in leading EAs out of local optima traps, and show that the proposed VDMGA is at least as efficient as nAMGA when applied to the range of our problems, being more efficient in very hard functions were traditional GAs usually fail to escape local optima. Also, scalability tests have been made that show VDMGA ability to decrease optimal population size, thus reducing the amount of evaluations needed to attain global optima. We like to stress that only two parameters need to be hand-tuned in VDMGA, thus reducing the tuning effort present in traditional GAs and nAMGA.     

基于多步强化变异算子的混合遗传算法

TSP是一类经典的NP-hard组合优化问题。通过引进多步强化变异算子MrM,提出了一种求解TSP实例的混合遗传算法MrMGA。多步强化变异是在单步强化变异策略的基础上进行了改进,通过向前考察几步个体进化效果,将该信息向回传递,影响个体变异策略。TSPLIB实例测试表明,MrMGA在求解小规模TSP实例时,其质量和求解速度都较EAX-GA有明显改进,从实验中得到折扣因子的值的变化对算法的影响。     

Truss optimization on shape and sizing with frequency constraints based on parallel genetic algorithm

Truss shape and sizing optimization under frequency constraints is extremely useful when improving the dynamic performance of structures. However, coupling of two different types of design variables, nodal coordinates and cross-sectional areas, often lead to slow convergence or even divergence. Because shape and sizing variables coupled increase the number of design variables and the changes of shape and sizing variables are of widely different orders of magnitude. Otherwise, multiple frequency constraints often cause difficult dynamic sensitivity analysis. Thus optimal criteria and mathematical programming methods have considerable limitations on solving the problems because of needing complex dynamic sensitivity analysis and being easily trapped into the local optima. Genetic Algorithms (GAs) show great potentials to solve the truss shape and sizing optimization problems. Since GAs adopt global probabilistic population search techniques and require no gradient information. The improved genetic algorithms can effectively increase the solution quality. However, the serial GA is computationally expensive and is limited on gaining higher quality solutions. To solve the truss shape and sizing optimization problems with frequency constraints more effectively and efficiently, a Niche Hybrid Parallel Genetic Algorithm (NHPGA) is proposed to significantly reduce the computational cost and to further improve solution quality. The NHPGA is to blend the advantages of parallel computing, simplex search and genetic algorithm with niche technique. Several typical truss optimization examples demonstrate that NHPGA can significantly reduce computing time and attain higher quality solutions. It also suggests that the NHPGA provide a potential algorithm architecture, which effectively combines the robust and global search characteristics of genetic algorithm, strong exploitation ability of simplex search and computational speedup property of parallel computing.     

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.     

一种高效的多目标演化算法

为了提高非劣解向Pareto最优前沿收敛的速度及进一步提高解的精度,在设计了一种新的杂交算子并改进了NSGA-Ⅱ的拥挤操作的基础上,提出了一种基于分级策略的多目标演化算法。数值实验表明,新算法能够非常高效地处理高维的最优前沿为凸的、非凸的和不连续前沿的多目标测试函数,得到的非劣解具有很好的分布性质。但在处理高维的具有太多局部最优前沿的多峰函数时极易陷入局部最优前沿。     

Theoretical proof of edge search strategy applied to power plantstart-up scheduling

Power plant start-up scheduling is aimed at minimizing the start-up time while limiting maximum turbine rotor stresses. This scheduling problem is highly nonlinear and has a number of local optima. In our previous research, we proposed an efficient search model: genetic algorithms (GAs) with enforcement operation to focus the search along the edge of the feasible space where the optimal schedule is supposed to stay. Based on a nonlinear dynamic simulation and a linear inverse calculation with the iteration method, the enforcement operation is applied to move schedules generated by GA toward the edge. We prove that the optimal schedule lies on the edge, ensuring that searching along the edge instead of the entire space can improve the search efficiency significantly without missing the optimum. Furthermore, we provide a theoretical setting equation for the inverse enforcement gains of the linear inverse calculation, intended to move schedules closer to the edge at each iteration of the enforcement operation. The theoretical setting equation is verified and discussed with the test results. We propose the theoretical setting equation with the test results as a guideline for the use of our proposed search model: GA with enforcement operation.     

PERFORMANCE EVALUATION OF GENETIC ALGORITHMS AND EVOLUTIONARY PROGRAMMING IN OPTIMIZATION AND MACHINE LEARNING

Genetic Algorithms (GAs) and Evolutionary Programming (EP) are investigated here in both optimization and machine learning. Adaptive and standard versions of the two algorithms are used to solve novel applications in search and rule extraction. Simulations and analysis show that while both algorithms may look similar in many ways their performance may differ for some applications. Mathematical modeling helps in gaining better understanding for GA and EP applications. Proper tuning and loading is a key for acceptable results. The ability to instantly adapt within an unpredictable and unstable search or learning environment is the most important feature of evolution-based techniques such as GAs and EP.     

Adaptive directed mutation for real-coded genetic algorithms

Adaptive directed mutation (ADM) operator, a novel, simple, and efficient real-coded genetic algorithm (RCGA) is proposed and then employed to solve complex function optimization problems. The suggested ADM operator enhances the abilities of GAs in searching global optima as well as in speeding convergence by integrating the local directional search strategy and the adaptive random search strategies. Using 41 benchmark global optimization test functions, the performance of the new algorithm is compared with five conventional mutation operators and then with six genetic algorithms (GAs) reported in literature. Results indicate that the proposed ADM-RCGA is fast, accurate, and reliable, and outperforms all the other GAs considered in the present study.     

Empirical investigation of the benefits of partial Lamarckianism

Genetic algorithms (GAs) are very efficient at exploring the entire search space; however, they are relatively poor at finding the precise local optimal solution in the region in which the algorithm converges. Hybrid GAs are the combination of improvement procedures, which are good at finding local optima, and GAs. There are two basic strategies for using hybrid GAs. In the first, Lamarckian learning, the genetic representation is updated to match the solution found by the improvement procedure. In the second, Baldwinian learning, improvement procedures are used to change the fitness landscape, but the solution that is found is not encoded back into the genetic string. This paper examines the issue of using partial Lamarckianism (i.e., the updating of the genetic representation for only a percentage of the individuals), as compared to pure Lamarckian and pure Baldwinian learning in hybrid GAs. Multiple instances of five bounded nonlinear problems, the location-allocation problem, and the cell formation problem were used as test problems in an empirical investigation. Neither a pure Lamarckian nor a pure Baldwinian search strategy was found to consistently lead to quicker convergence of the GA to the best known solution for the series of test problems. Based on a minimax criterion (i.e., minimizing the worst case performance across all test problem instances), the 20% and 40% partial Lamarckianism search strategies yielded the best mixture of solution quality and computational efficiency.     

一种函数优化问题的混合遗传算法

将传统的局部搜索算法和遗传算法相结合,可以较好地解决遗传算法在达到全局最优解前收敛慢的问题.文章给出一种结合可变多面体法和正交遗传算法的混合算法.实验表明,它通过对问题的解空间交替进行全局和局部搜索,能更有效地求解函数优化问题.     

A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating - a type of non-random mating in which individuals are chosen according to their similarities - may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune.     

Using parallelization and hardware concurrency to improve the performance of a genetic algorithm

Genetic algorithms (GAs) are powerful tools for solving many problems requiring the search of a solution space having both local and global optima. The main drawback for GAs is the long execution time normally required for convergence to a solution. This paper discusses three different techniques that can be applied to GAs to improve overall execution time. A serial software implementation of a GA designed to solve a task scheduling problem is used as the basis for this research. The execution time of this implementation is then improved by exploiting the natural parallelism present in the algorithm using a multiprocessor. Additional performance improvements are provided by implementing the original serial software GA in dedicated reconfigurable hardware using a pipelined architecture. Finally, an advanced hardware implementation is presented in which both pipelining and duplicated hardware modules are used to provide additional concurrency leading to further performance improvements. Copyright © 2006 John Wiley & Sons, Ltd.     

Enhancing genetic algorithms for dependent job scheduling in grid computing environments

Genetic Algorithms (GAs) are stochastic search techniques based on principles of natural selection and recombination that attempt to find optimal solutions in polynomial time by manipulating a population of candidate solutions. GAs have been widely used for job scheduling optimisation in both homogeneous and heterogeneous computing environments. When compared with list scheduling heuristics, GAs can potentially provide better solutions but require much longer processing time and significant experimentation to determine GA parameters. This paper presents a GA for scheduling dependent jobs in grid computing environments. A?number of selection and pre-selection criteria for the GA are evaluated with an aim to improve GA performance in job scheduling optimization. A?Task Matching with Data scheme is proposed as a GA mutation operator. Furthermore, the effect of the choice of heuristics for seeding the GA is investigated.     

Fuzzy genetic sharing for dynamic optimization

Recently,genetic algorithms(GAs) have been applied to multi-modal dynamic optimization(MDO).In this kind of optimization,an algorithm is required not only to find the multiple optimal solutions but also to locate a dynamically changing optimum.Our fuzzy genetic sharing(FGS) approach is based on a novel genetic algorithm with dynamic niche sharing(GADNS).FGS finds the optimal solutions,while maintaining the diversity of the population.For this,FGS uses several strategies.First,an unsupervised fuzzy clustering method is used to track multiple optima and perform GADNS.Second,a modified tournament selection is used to control selection pressure.Third,a novel mutation with an adaptive mutation rate is used to locate unexplored search areas.The effectiveness of FGS in dynamic environments is demonstrated using the generalized dynamic benchmark generator(GDBG).