Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.     

A Hybrid Genetic Algorithm for Nonconvex Function Minimization

In this paper, we consider the problem of minimizing a function in severalvariables which could be multimodal and may possess discontinuities. A newalgorithm for the problem based on the genetic technique is developed. Thealgorithm is hybrid in nature in the sense that it utilizes the genetictechnique to generate search directions, which are used in an optimizationscheme and is thus different from any other methods in the literature.The algorithm has been tested on the Rosenbrock valley functions in 2 and 4dimensions, and multimodal functions in 2 and 4 dimensions, which are of ahigh degree of difficulty. The results are compared with the Adaptive RandomSearch, and Simulated Annealing algorithms. The performance of the algorithmis also compared to recent global algorithms in terms of the number offunctional evaluations needed to obtain a global minimum and results show thatthe proposed algorithm is better than these algorithms on a set of standardtest problems. It seems that the proposed algorithm is efficient and robust.     

Comparison of One-dimensional Composite and Non-composite Passive Algorithms

In this paper we analyze composite non-adaptive algorithms for optimization of one-dimensional Brownian motion. We show that a composite deterministic algorithm has a better average performance than the best random one.     

遗传算法、差分演化和一个处理约束的映射

S.Koziel和Z.Michalewicz(1999年)提出了一个处理约束的映射,研究该映射与不同算法相结合后的不同的代数结构.从理论上证明了当其与遗传算法相结合时,该映射是同构映射,而在差分演化算法的变异操作下,该映射不是同态映射,更不是同构映射.进而表明,该映射更适宜于与遗传算法相结合,而并不太适宜于与差分演化算法(及其类似的算法)相结合。     

Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

An exact penalty function method with global convergence properties for nonlinear programming problems

In this paper a new continuously differentiable exact penalty function is introduced for the solution of nonlinear programming problems with compact feasible set. A distinguishing feature of the penalty function is that it is defined on a suitable bounded open set containing the feasible region and that it goes to infinity on the boundary of this set. This allows the construction of an implementable unconstrained minimization algorithm, whose global convergence towards Kuhn-Tucker points of the constrained problem can be established.     

A computational study on different penalty approaches for solving constrained global optimization problems with the electromagnetism-like method

In this article, the application of the electromagnetism-like method (EM) for solving constrained optimization problems is investigated. A number of penalty functions have been tested with EM in this investigation, and their merits and demerits have been discussed. We have also provided motivations for such an investigation. Finally, we have compared EM with two recent global optimization algorithms from the literature. We have shown that EM is a suitable alternative to these methods and that it has a role to play in solving constrained global optimization problems.     

Extended Fuzzy C-Means and Genetic Algorithms to Optimize Power Flow Management in Hybrid Electric Vehicles

The need for personal transportation must be harmonized by considering the impact of so huge number of vehicles on the environment. The adoption of hybrid electric vehicles can provide a sensible improvement from an environmental viewpoint, but at the same time makes more difficult the definition and implementation of the overall powertrain control mechanism. In fact, powertrain control problems are known to be very complex due to conflicting requirements, and this difficulty augments in case of hybrid electric vehicles. Most of the features of the future hybrid electric vehicles are enabled by a new energy flow management unit designed to split the instantaneous power demand between the internal combustion engine and the electric motor, ensuring both an efficient power supply and reduced emissions. Classic approaches that rely on static thresholds, optimized on a fixed drive cycle, cannot face the high dynamicity and unpredictability of real-life drive conditions. The need to actually control a real vehicle stimulates the research of innovative methodologies for the real-time identification of the operating points of each energy source. This paper is framed into this context: after a brief discussion about a non-conventional formalization of the energy flows problem based on a multiobjective function, a knowledge-based control system for splitting the vehicle's power demand between the engine and motor is presented. The proposed approach exploits a fuzzy clustering criterion that combined with a genetic algorithm, permits to achieve better results, both in terms of a reduced computational effort and an improved efficiency of the control system over various driving cycles. To validate the proposed approach, simulation tests and comparisons with other energy management strategies are discussed.     

GA算子的代数模型

采用矩阵形式表示遗传操作过程 ,可为遗传算法程序设计提供简明的数学模型     

基于模矢搜索和遗传算法的混合约束优化算法

近年,免梯度方法又开始引起大家的注意，由于不需要计算函数的梯度．特别适合用来求解那些无法得到梯度信息或需要花很大计算量才能得到梯度信息的问题．本文构造了一个基于模矢搜索和遗传算法的混合优化算法．在模矢搜索方法的搜索步，用一个类似于遗传算法的方法产生一个有限点集．算法是全局收敛的.     

Some Simple Algorithms for Structural Comparison

Structural comparison (i.e., the simultaneous analysis of multiple structures) is a problem which arises frequently in such diverse arenas as the study of organizational forms, social network analysis, and automated text analysis. Prior work has demonstrated the applicability of a range of standard multivariate analysis procedures to the structural comparison problem. Here, some simple algorithms are provided which elucidate several of these methods in an easily implemented form. Carter T. Butts is Assistant Professor at the University of California-Irvine in the Department of Sociology, and is a member of the Institute for Mathematical Behavioral Sciences and the California Institute for Telecommunications and Information Technology. His current research focuses on communication during disasters, Bayesian inference for network data, network comparison, and the structure of spatially embedded interpersonal networks. Kathleen M. Carley is Professor at Carnegie Mellon University, with appointments in the Institute for Software Research International, the H.J. Heinz III School of Public Policy and Management, and the Department of Engineering and Public Policy. Her research centers around areas of social, organizational, knowledge and information networks, organizational design, change, adaptivity and and performance, computational organization theory, crisis management, social theory, impacts on information diffusion of changes in social policy and changes in communication technology, and mapping experts' and executives' knowledge networks using textual analysis techniques.     

一个水流问题的遗传算法求解

应用遗传算法(GA)来讨论一个水流问题.这个水流问题曾是不少统计学者用来考察不同试验设计和建模方法的常用案例.通过本例旨在说明遗传算法确为求解复杂系统优化问题的有力工具.     

Ordered events games on graphs admitting chance moves

The games on finite graphs having chance moves are considered. The preferences are given by the partial ordering at the set of plays. The existence of equilibrium points of these games is proved.     

二层随机规划基于随机模拟的遗传算法

本提出了二层随机规划模型，给出了求解二层随机规划问题的基于随机模拟的遗传算法。实际算例表明算法是可行的、有效的。     

基于遗传算法的多目标可靠性优化

在元件的体积、重量和造价的共同约束下的多级串并联系统的可靠性优化问题是一个具有多局部极值的、非线性的、同时具有整数和实数变量的混合优化问题.将遗传算法和多目标可靠性分配问题相结合,对可靠性分配问题进行求解,得到较好效果,从而得出结论,遗传算法在求解多目标可靠性优化问题中是一种行之有效的方法.     

遗传算法在林木采伐作业信息管理中的应用

遗传算法是基于生物学进化原理的一种新的优化算法,本文介绍了遗传算法在林木采伐信息管理上的应用,通过林木采伐生产作业的衔接紧密的实际例子,论述了该方法在生产任务安排,降伐运输成本及劳力分配等信息管理中的作用。     

Crossing Over Genetic Algorithms: The Sugal Generalised GA

Sugal is a major new public-domain software package designed to support experimentation with, and implementation of, Genetic Algorithms. Sugal includes a generalised Genetic Algorithm, which supports the major popular versions of the GA as special cases. Sugal also has integrated support for various datatypes, including real numbers, and features to make hybridisation simple. This paper discusses the Sugal GA, showing how recombining the features of the popular algorithms results in the creation of a number of useful hybrid algorithms.     

基于遗传算法的对规避目标搜索模型

分析了在应召条件下对规避目标搜索行动的特点,然后采用遗传算法建立了可用于辅助搜索决策者制定协同搜索方案的模型,为分析应召搜索提供了新的方法,该方法克服了传统的运筹学搜索论在协同行动等复杂条件下寻求最优搜索方案的不足     

A Numerical Comparison of Some Modified Controlled Random Search Algorithms

In this paper we propose a new version of the Controlled Random Search(CRS) algorithm of Price. The new algorithmhas been tested on thirteen global optimization test problems. Numericalexperiments indicate that the resulting algorithm performs considerablybetter than the earlier versions of the CRS algorithms. The algorithm,therefore, could offer a reasonable alternative to many currently availablestochastic algorithms, especially for problems requiring direct searchtype methods. Also a classification of the CRS algorithms is made based onglobal technique – local technique and the relative performance ofclasses is numerically explored.