Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.     

Parallel processing in dynamic simulation of power systems

The dynamic behaviour of a large interconnected electric power system is characterized by a simultaneous set of nonlinear algebraic and ordinary differential equations. The solution is obtained by numerical methods and the simulation of the transient behaviour for a few seconds after a fault is the standard analytical procedure used in planning and operational studies of the system. The need for on-line simulation in near real time for more efficient operation has encouraged the search for faster solution methods and the use of parallel computers for this purpose has attracted the attention of many researchers. The success of parallelization depends on three factors: the problem structure, the computer architecture, and the algorithm that takes maximum advantage of both. In this problem, the generator equations are only coupled through the electrical network providing some parallelization in (variable) space, and a solution is needed at each time step leading to some parallelization in time (waveform relaxation). However, since the problem formulation is not completely decoupled, parallel algorithms can only be developed by trading off any relaxation with a degradation in convergence. The fastest sequential algorithm used today is the combination of implicit trapezoidal integration with a dishonest Newton solution. The Newton algorithm is not parallel at all but has the fastest convergence while a Gauss-Jacobi algorithm is completely parallel but converges very slowly. A relaxation of the Newton algorithm appears to be a good compromise. As for the parallel hardware, the coupling seems to require significant communication between processors thus favouring a data-sharing architecture over a message-passing hypercube. Special architectures to match the problem structure have also been an area of investigation. This paper elaborates on the above issues and assesses the present state-of-the-art.     

FUZZY-GENETIC ALGORITHMS AND TIME-OPTIMAL OBSTACLE-FREE PATH GENERATION FOR MOBILE ROBOTS

This paper, describes a new yet efficient technique based on fuzzy logic and genetic algorithms (Gas) to solve the find-path problems of a mobile robot, which is formulated as a nonlinear programming problem. In the proposed algorithm, a fuzzy logic controller is used to find obstracle-free directions locally and GAs are used as optimizer to find optimal/near-optimal locations along the obstracle-free directions. This algorithm is found to be more efficient than a steepest gradient descent method. Although the fuzzy-GA method is shown to find slightly inferior or similar solutions to those found using the best-known tangent-graph and A* algorithms, it is computationally faster than them. Moreover, the fuzzy-GA approach is practically more viable than the tangent-graph method, because of former's lesser sensitivity to the number and type of obstacles. The efficiency of the proposed method demonstrated in this paper suggests that it can be extended to solve motion planning problems having moving obstacles.     

Genetic-algorithms-based algorithm portfolio for inventory routing problem with stochastic demand

This paper presents an algorithm portfolio methodology based on evolutionary algorithms to solve complex dynamic optimisation problems. These problems are known to have computationally complex objective functions, which make their solutions computationally hard to find, when problem instances of large dimensions are considered. This is due to the inability of the algorithms to provide an optimal or near-optimal solution within an allocated time interval. Therefore, this paper employs a bundle of evolutionary algorithms (EAs) tied together with several processors, known as an algorithm portfolio, to solve a complex optimisation problem such as the inventory routing problem (IRP) with stochastic demands. EAs considered for algorithm portfolios are the genetic algorithm and its four variants such as the memetic algorithm, genetic algorithm with chromosome differentiation, age-genetic algorithm, and gender-specific genetic algorithm. In order to illustrate the applicability of the proposed methodology, a generic method for algorithm portfolios design, evaluation, and analysis is discussed in detail. Experiments were performed on varying dimensions of IRP instances to validate different properties of algorithm portfolio. A case study was conducted to illustrate that the set of EAs allocated to a certain number of processors performed better than their individual counterparts.     

Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints

This study involves an unrelated parallel machine scheduling problem in which sequence-dependent set-up times, different release dates, machine eligibility and precedence constraints are considered to minimize total late works. A new mixed-integer programming model is presented and two efficient hybrid meta-heuristics, genetic algorithm and ant colony optimization, combined with the acceptance strategy of the simulated annealing algorithm (Metropolis acceptance rule), are proposed to solve this problem. Manifestly, the precedence constraints greatly increase the complexity of the scheduling problem to generate feasible solutions, especially in a parallel machine environment. In this research, a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. The performance of the proposed algorithms is evaluated in numerical examples. The results indicate that the suggested hybrid ant colony optimization statistically outperformed the proposed hybrid genetic algorithm in solving large-size test problems.     

Scatter search and star-paths: beyond the genetic metaphor

Scatter search and genetic algorithms have originated from somewhat different traditions and perspectives, yet exhibit features that are strongly complementary. Links between the approaches have increased in recent years as variants of genetic algorithms have been introduced that embody themes in closer harmony with those of scatter search. Some researchers are now beginning to take advantage of these connections by identifying additional ways to incorporate elements of scatter search into genetic algorithm approaches. There remain aspects of the scatter approach that have not been exploited in conjunction with genetic algorithms, yet that provide ways to achieve goals that are basic to the genetic algorithm design. Part of the gap in implementing hybrids of these procedures may derive from relying too literally on the genetic metaphor, which in its narrower interpretation does not readily accommodate the strategic elements underlying scatter search. The theme of this paper is to show there are benefits to be gained by going beyond a perspective constrained too tightly by the connotations of the term genetic. We show that the scatter search framework directly leads to processes for combining solutions that exhibit special properties for exploiting combinatorial optimization problems. In the setting of zero-one integer programming, we identify a mapping that gives new ways to create combined solutions, producing constructions calledstar-paths for exploring the zero-one solution space. Star-path trajectories have the special property of lying within regions assured to include optimal solutions. They also can be exploited in association with both cutting plane and extreme point solution approaches. These outcomes motivate a deeper look into current conceptions of appropriate ways to combine solutions, and disclose there are more powerful methods to derive information from these combinations than those traditionally applied.This research is supported in part by the Joint Air Force Office of Scientific Research and Office of Naval Research Contract No. F49620-90-C-0033 at the University of Colorado     

Optimisation of cutting parameters using a multi-objective genetic algorithm

This paper presents a new optimisation technique based on genetic algorithms (GA) for determination of cutting parameters in machining operations. The cutting parameters considered in this study are cutting speed, feed rate and cutting depth. The effect of these parameters on production time, production cost and roughness is mathematically formulated. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. Experimental results show that the proposed algorithm is both effective and efficient, and can be integrated into an intelligent process planning system for solving complex machining optimisation problems.     

A constraint consensus memetic algorithm for solving constrained optimization problems

Constraint handling is an important aspect of evolutionary constrained optimization. Currently, the mechanism used for constraint handling with evolutionary algorithms mainly assists the selection process, but not the actual search process. In this article, first a genetic algorithm is combined with a class of search methods, known as constraint consensus methods, that assist infeasible individuals to move towards the feasible region. This approach is also integrated with a memetic algorithm. The proposed algorithm is tested and analysed by solving two sets of standard benchmark problems, and the results are compared with other state-of-the-art algorithms. The comparisons show that the proposed algorithm outperforms other similar algorithms. The algorithm has also been applied to solve a practical economic load dispatch problem, where it also shows superior performance over other algorithms.     

Parallel computational strategies for structural optimization

The objective of this paper is to investigate the efficiency of various computational algorithms implemented in the framework of structural optimization methods based on evolutionary algorithms. In particular, the efficiency of parallel computational strategies is examined with reference to evolution strategies (ES) and genetic algorithms (GA). Parallel strategies are implemented both at the level of the optimization algorithm, by exploiting the natural parallelization features of the evolutionary algorithms, as well as at the level of the repeated structural analysis problems that are required by ES and GA. In the latter case the finite element solutions are performed by the FETI domain decomposition method specially tailored to the particular type of problems at hand. The proposed methodology is generic and can be applied to all types of optimization problems as long as they involve large‐scale finite element simulations. The numerical tests of the present study are performed on sizing optimization of skeletal structures. The numerical tests demonstrate the computational advantages of the proposed parallel strategies, which become more pronounced in large‐scale optimization problems. Copyright © 2003 John Wiley & Sons, Ltd.     

A problem space algorithm for single machine weighted tardiness problems

We propose a problem space genetic algorithm to solve single machine total weighted tardiness scheduling problems. The proposed algorithm utilizes global and time-dependent local dominance rules to improve the neighborhood structure of the search space. They are also a powerful exploitation (intensifying) tool since the global optimum is one of the local optimum solutions. Furthermore, the problem space search method significantly enhances the exploration (diversification) capability of the genetic algorithm. In summary, we can improve both solution quality and robustness over the other local search algorithms reported in the literature.     

基于批量划分的无等待流水车间订单接受问题研究

在无等待流水车间环境下,考虑订单分批量加工策略的订单接受问题,建立问题的数学模型。由于问题的NP难特性,提出改进的遗传算法对模型进行求解。改进的算法采用正向和反向NEH算法与随机方法产生初始种群,在算法更新过程中将禁忌搜索算法嵌入到遗传算法中来实现局部搜索,避免算法陷入局部最优。最后,算例表明批量划分策略能够有效减少订单的完成时间,实现订单总收益的最大化。通过算法对比,说明了改进遗传算法具有较好的求解效果。     

A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem

The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-known instances from the QAPLIB library. By increasing the number of processors, generations and population sizes we have been able to find solutions that are the same as (or very close to) the best reported solutions for large QAP instances in QAPLIB. In order to parallelise the Genetic Algorithm we generate and evolve separate solution pools on each cluster processor, using an island model. This model exchanges 10% of each processor’s solutions at the initial stages of optimisation. We show experimentally that both execution times and solution qualities are improved for large QAP instances by using our Island Parallel Genetic Algorithm.     

A multi-objective genetic algorithm approach to the design of cellular manufacturing systems

In this paper, a multi-objective integer programming model is constructed for the design of cellular manufacturing systems with independent cells. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. There are some features that make the proposed algorithm different from other algorithms used in the design of cellular manufacturing systems. These include: (1) a systematic uniform design-based technique, used to determine the search directions, and (2) searching the solution space in multiple directions instead of single direction. Four problems are selected from the literature to evaluate the performance of the proposed approach. The results validate the effectiveness of the proposed method in designing the manufacturing cells.     

Optimising resource portfolio planning for capital-intensive industries under process-technology progress

This paper addresses the problem of resource portfolio planning of firms in high-tech, capital-intensive manufacturing industries. In light of the strategic importance of resource portfolio planning in these industries, we offer an alternative approach to modelling capacity planning and allocation problems that improves the deficiencies of prior models in dealing with three salient features of these industries, i.e. fast technological obsolescence, volatile market demand, and high capital expenditure. This paper first discusses the characteristics of resource portfolio planning problems including capacity adjustment and allocation. Next, we propose a new mathematical programming formulation that simultaneously optimises capacity planning and task assignment. For solution efficiency, a constraint-satisfied genetic algorithm (CSGA) is developed to solve the proposed mathematical programming problem on a real-time basis. The proposed modelling scheme is employed in the context of a semiconductor testing facility. Experimental results show that our approach can solve the resource portfolio planning problem more efficiently than a conventional optimisation solver. The overall contribution is an analytical tool that can be employed by decision makers responding to the dynamic technological progress and new product introduction at the strategic resource planning level.     

A BEM‐based genetic algorithm for identification of polarization curves in cathodic protection systems

The purpose of this work is to apply an inverse boundary element formulation in order to develop efficient algorithms for identification of polarization curves in a cathodic protection system. The problem is to minimize an objective function measuring the difference between observed and BEM‐predicted surface potentials. The numerical formulation is based on the application of genetic algorithms, which are robust search techniques emulating the natural process of evolution as a means of progressing towards an optimum solution. Examples of application are included in the paper for different types of polarization curves in finite and infinite electrolytes. The accuracy and efficiency of the numerical results are verified by comparison with standard conjugate gradient techniques. As a result of this research, the genetic algorithm approach is shown to be more robust, independent of the position of the sensors and of initial guesses, and will be further developed for three‐dimensional applications. Copyright © 2002 John Wiley & Sons, Ltd.     

遗传禁忌搜索算法在混流装配线排序中的应用

针对混流装配线排序问题，提出了一种混合遗传禁忌搜索算法，在每一代遗传演化之后，按一定比例随机选择部分解进行禁总搜索，以提高算法的全局搜索能力和收敛性。通过一个混流装配线排序实验，分别利用遗传算法和遗传禁忌搜索算法进行求解，结果表明遗传禁忌搜索算法具有更好的全局搜索能力和收敛性能。     

JIT mixed-model sequencing with batching and setup considerations via search heuristics

This research addresses the problem of sequencing items for production when it is desired that the production sequences result in minimal usage rates–surrogate measures for flexibility in a JIT environment. While seeking sequences with minimal usage rates, the number of required setups for the sequences is also considered, along with feasible batch-sizing combinations. The general intent is to find minimum usage-rate sequences for each associated number of setups and total batches. This multiple objective problem is addressed via a three-dimensional efficient frontier. Because the combinatorial nature of sequencing problems typically provides an intractable search space for problems of ‘real world’ size, the search heuristics of simulated annealing and genetic algorithms are presented and used to find solutions for several problem sets from the literature. Experimentation shows that the simulated annealing approach outperforms the genetic algorithm approach in both objective function and CPU performance.     

A modified harmony search algorithm for the multi-objective flowshop scheduling problem with due dates

This paper presents a modified harmony search optimisation algorithm (MHSO), specifically designed to solve two- and three-objective permutation flowshop scheduling problems, with due dates. To assess its capability, five sets of scheduling problems have been used to compare the MHSO with a known and highly efficient genetic algorithm (GA) chosen as the benchmark. Obtained results show that the new procedure is successful in exploring large regions of the solution space and in finding a significant number of Pareto non-dominated solutions. For those cases where the exhaustive evaluation of sequences can be applied the algorithm is able to find the whole non-dominated Pareto border, along with a considerable number of solutions that share the same optimal values for the considered optimisation parameters. To validate the algorithm, five sets of scheduling problems are investigated in-depth in comparison with the GA. Results obtained by both methods (exhaustive solutions have been provided as well for small sized problems) are fully described and discussed.     

Matheuristic approaches for Q-coverage problem versions in wireless sensor networks

This article deals with sensor coverage scheduling in wireless sensor networks subject to Q-coverage constraints. The main concern is to maximize the network lifetime, while ensuring that each target is covered by a given number of sensors. Three different variations of this problem are considered. Column generation based exact approaches are developed for those problems where the auxiliary problem is solved by a two-level approach comprising a genetic algorithm and an integer linear programming formulation. The genetic algorithm takes advantage of the auxiliary problem structure and appears to be very efficient at providing the master problem with attractive columns. The auxiliary problem integer linear programming (ILP) formulation is then mostly used for proving the optimality status of the current master problem solution. The proposed approaches are shown to be significantly faster than column generation approaches relying only on the auxiliary problem ILP formulation.     

An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts

Puzzle-based storage systems consist of densely stored unit loads on a square grid. The problem addressed in this paper is to retrieve a stored unit load from a puzzle-based storage using the minimum number of item moves. While previous research contributed optimal algorithms for only up to two empty locations (escorts), our approach solves configurations where multiple empty locations are arbitrarily positioned in the grid. The problem is formulated as a state space problem and solved to optimality using an exact search algorithm. To reduce the search space, we derive bounds on the number of eligible empty locations and develop several search-guiding estimate functions. Furthermore, we present a heuristic variant of the search algorithm to solve larger problem instances. We evaluate both solution algorithms on a large set of problem instances. Our computational results show that the algorithms clearly outperform existing approaches where they are applicate and solve more general configurations, which could not be solved to optimality before. The heuristic variant efficiently yields high-quality solutions for significantly larger instances of practically relevant size.