Genetic algorithms for solving the discrete ordered median problem

In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.     

Kinematical synthesis of 1-dof mechanisms using finite elements and genetic algorithms

The use of finite elements in both kinematic analysis and synthesis of mechanisms has shown good performance. Its only drawback is the need for an initial reasonable quality solution.

To address this topic, the use of genetic algorithms with a finite-element-based error function is proposed in this paper. This approach has not only shown good behaviour with simple mechanisms, but also with complex kinematic chains.

The energy-based error function, which has demonstrated such good behaviour in the optimization via second-order Newton–Raphson methods, presented some limitations. To solve them, a new distance-based error function has been developed. Simultaneously, new finite elements have been created to represent some joints and kinematic elements. The need to address some specific configuration problems has led to the development of a correction algorithm.     

Genetic algorithms in statistical tolerancing

An important aspect in manufacturing design is the distribution of geometrical tolerances so that an assembly functions with given probability, while minimising the manufacturing cost. This requires a complex search over a multidimensional domain, much of which leads to infeasible solutions and which can have many local minima. As well, Monte-Carlo methods are often required to determine the probability that the assembly functions as designed. This paper describes a genetic algorithm for carrying out this search and successfully applies it to two specific mechanical designs, enabling comparisons of a new statistical tolerancing design method with existing methods.     

On genetic algorithms for the packing of polygons

A genetic algorithm for placing polygons on a rectangular board is proposed. The algorithm is improved by combination with deterministic methods.     

Genetic algorithms and cellular automata in aquifer management

A groundwater management problem is presented involving pumping cost minimization with both well discharges and well locations as decision variables. A grid of candidate well locations is set up and optimal arrangements of wells are sought within this discrete space. A genetic algorithm approach is presented with the following particular features: (a) A suitable scaling is applied to the objective function in order to alleviate its regionally flat behavior. (b) No penalty functions are involved in constraint handling. Instead, the feasible region is transformed into a rectangular domain. The transformation introduced is proved to be bijective. (c) A binary representation of well configurations is presented and compared to a combinatorial one. The binary representation necessitates the introduction of specially designed genetic operators. Besides purely genetic algorithms, the concept of cellular automaton is introduced as the basis of an alternative formulation of the optimization problem. The lattice of the cellular automaton provides the discrete set of candidate well positions. The well configuration is represented by a group of agents occupying an equal number of lattice sites. The agents change positions as dictated by the structure of the automaton and, also, by an associated genetic algorithm, which directs the evolution of the whole scheme toward an optimal configuration. An improved performance of this approach is noted and discussed in comparison to the purely genetic algorithm schemes of the present work. A simulated annealing approach is also applied to the same problem for comparison purposes. Finally, a new and more efficient hybrid annealing–genetic approach is introduced and discussed.     

Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder

Two variants of genetic algorithm (GA) for solving the Supply Management Problem with Lower-Bounded Demands (SMPLD) are proposed and experimentally tested. The SMPLD problem consists in planning the shipments from a set of suppliers to a set of customers minimizing the total cost, given lower and upper bounds on shipment sizes, lower-bounded consumption and linear costs for opened deliveries. The first variant of GA uses the standard binary representation of solutions and a new recombination operator based on the mixed integer programming (MIP) techniques. The second GA is based on the permutation representation and a greedy decoder. Our experiments indicate that the GA with MIP-recombination compares favorably to the other GA and to the MIP-solver CPLEX 9.0 in terms of cost of obtained solutions. The GA based on greedy decoder is shown to be the most robust in finding feasible solutions.     

Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete

The coordination of just-in-time production and transportation in a network of partially independent facilities to guarantee timely delivery to distributed customers is one of the most challenging aspect of supply chain management. From a theoretical perspective, the timely production/distribution can be viewed as a hybrid combination of planning, scheduling and routing problems, each notoriously affected by nearly prohibitive combinatorial complexity. From a practical viewpoint, the problem calls for a trade-off between risks and profits. This paper focuses on the ready-mixed concrete delivery: in addition to the mentioned complexity, strict time-constraints forbid both earliness and lateness of the supply. After developing a detailed model of the considered problem, we propose a novel meta-heuristic approach based on a hybrid genetic algorithm combined with constructive heuristics. A detailed case study derived from industrial data is used to illustrate the potential of the proposed approach.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.     

The use of genetic algorithms to solve the economic lot size scheduling problem

The purpose of this paper is to investigate the use genetic algorithms (GAs) for solving the Economic Lot Size Scheduling Problem (ELSP). The ELSP is formulated using the Basic Period (BP) approach which results in a problem having one continuous decision variable and a number of integer decision variables equal to the number of products being produced. This formulation is ideally suited for using GAs. The GA is tested on Bomberger's classical problem. The resulting solutions were better than those obtained using an iterative dynamic programming (DP) approach. The total cost of GA solutions to the problem with utilization up to 65% were within 3.4% of the lower bound. The GA also performed well for higher utilization yielding solutions within 13.87% of the lower bound for utilization up to 86%. The GA was tested on a 30-item problem and good solutions were obtained. The results of the GA under different binary representations, crossover methods, and initialization methods are compared to identify the best settings. The results indicate that for this particular problem, binary representation works better than Gray coding, 2-point crossover is best, and an infeasible starting population is better than feasible.     

Genetic algorithms for the 2-page book drawing problem of graphs

The minimisation of edge crossings in a book drawing of a graph is one of the important goals for a linear VLSI design, and the 2-page crossing number of a graph provides an upper bound for the standard planar crossing number. We design genetic algorithms for the 2-page drawings, and test them on the benchmark test suits, Rome graphs and Random Connected Graphs. We also test some circulant graphs, and get better results than previously presented in the literature. Moreover, we formalise three conjectures for certain kinds of circulant graphs,supported by our experimental results.     

A distance based rule for removing population members in genetic algorithms

In this paper we propose a new rule for removal of population members. We tested the new approach for solving the Quadratic Assignment Problem with excellent results.Received: January 2005, AMS classification: 68T20, 90C59     

Genetic algorithms for the traveling salesman problem

This paper is a survey of genetic algorithms for the traveling salesman problem. Genetic algorithms are randomized search techniques that simulate some of the processes observed in natural evolution. In this paper, a simple genetic algorithm is introduced, and various extensions are presented to solve the traveling salesman problem. Computational results are also reported for both random and classical problems taken from the operations research literature.     

遗传算法的改进与实现

本文在对遗传算法基本思想进行介绍的基础上,对具体的操作过程进行了改进,并给出了具体程序设计方法。     

Solving the knapsack problem with imprecise weight coefficients using genetic algorithms

This paper investigates solving the knapsack problem with imprecise weight coefficients using genetic algorithms. This work is based on the assumption that each weight coefficient is imprecise due to decimal truncation or coefficient rough estimation by the decision-maker. To deal with this kind of imprecise data, fuzzy sets provide a powerful tool to model and solve this problem. We investigate the possibility of using genetic algorithms in solving the fuzzy knapsack problem without defining membership functions for each imprecise weight coefficient. The proposed approach simulates a fuzzy number by distributing it into some partition points. We use genetic algorithms to evolve the values in each partition point so that the final values represent the membership grade of a fuzzy number. The empirical results show that the proposed approach can obtain very good solutions within the given bound of each imprecise weight coefficient than the fuzzy knapsack approach. The fuzzy genetic algorithm concept approach is different, but gives better results than the traditional fuzzy approach.     

混合遗传算法收敛性分析

针对遗传算法爬山能力弱但合局搜索能力强的特点 ,本文将遗传算法嵌入到基入传统优化的拟下降算法中 ,并对算法的拟下降步骤做了一定的改进 ,使得整个算法具有全局收敛性 .本文采用马尔可夫的观点进一步证明了算法的全局收敛性 ,并用极难优化的测试函数给出了数值算例 ,证明了本文算法为一种可行的全局优化算法 .     

改进的多目标规划遗传算法

本讨论了[1]中多目标规划遗传算法存在的缺陷，并提出了相应改进策略．这些策略包括：引进精粹策略，杂交限制，终止条件，个体表示改进等方面，利用这些策略使算法能克服终止准则和小生境聚集的缺陷，使得算法能更快的收敛到Pareto最优解集同时又有好有分布的Pareto最优解集．     

Solving a concrete sleepers production scheduling by genetic algorithms

PRECON S.A. is a manufacturing company devoted to produce prefabricated concrete parts for several industries as railway transportation and agricultural industries. Recently, PRECON S.A. signed a contract with RENFE, the Spanish National Railway Company, to manufacture pre-stressed concrete sleepers for the sidings of the new railways of the high speed train (AVE). The scheduling problem associated with the manufacturing process of the sleepers is very complex, since this involves several constraints and objectives. These constraints are related to production capacity, the quantity of available moulds, demand satisfaction and other operational constraints. The two main objectives are related to the way to maximize the utilization of manufacturing resources and minimize mould movements. We developed a deterministic crowding genetic algorithm for this multiobjective problem. The algorithm has proved to be a powerful and flexible tool to solve large-scale instances of this real and complex scheduling problem.     

混沌遗传算法

利用混沌序列来构造遗传算子,使不同代之间从短期看似随机的,而从长期看则存在着一种“精致”地内在关系,由此获得了一系列基于混沌序列的遗传算法,这些算法对克服标准遗传算法中的一些不足是有利的,更重要是将混沌引入遗传算法的新思路。     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

A learning process for fuzzy control rules using genetic algorithms

The purpose of this paper is to present a genetic learning process for learning fuzzy control rules from examples. It is developed in three stages: the first one is a fuzzy rule genetic generating process based on a rule learning iterative approach, the second one combines two kinds of rules, experts rules if there are and the previously generated fuzzy control rules, removing the redundant fuzzy rules, and the thrid one is a tuning process for adjusting the membership functions of the fuzzy rules. The three components of the learning process are developed formulating suitable genetic algorithms.