Solving inverse initial-value, boundary-value problems via genetic algorithm

There is a growing interest in inverse initial-value, boundary-value (inverse IVBV) problems, and in the development of robust, computationally efficient methods suitable for their solution. Inverse problems are prominent in science and engineering where often an effect is measured and the cause is not known; scientists and engineers observe the response of a system and desire to know the particulars of the system that elicited such a response. IVBV problems result when the equations that govern the behavior of a system are partial differential equations (wave phenomena, diffusion, potential of all kinds, etc.). Thus, inverse IVBV problems stem from systems governed by partial differential equations in which a response has been measured and a characteristic of the system must be computed. In this paper, an approach to solving inverse IVBV problems is presented in which the stated problem is transformed into a nonlinear optimization problem which is then solved using a genetic algorithm. Results are presented demonstrating the effectiveness of this approach for solving inverse problems that result from systems governed by three specific partial differential (1) the heat equation, (2) the wave equation, and (3) Poisson’s equation.     

Evolution of a vision system by genetic algorithm

This paper proposes a framework for a genetic algorithm applied to determine and construct an organ, especially the neural network of a virtual creature. The vision system of the creature is a result of genetic evolution, and we are trying to realize this on the computer. We examine how the visual organ of the animal is evolved under a special environment (e.g., the specialized visual organ of an animal to catch a moving insect), and how many variations of neural networks exist. We also think it is possible to generalize the method to an automatic generation of various kinds of visual recognition system by adding various kinds of evolution any directions. This work was presented, in part, at the Second International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1997     

Hybrid genetic algorithm for optimization problems with permutation property

Permutation property has been recognized as a common but challenging feature in combinatorial problems. Because of their complexity, recent research has turned to genetic algorithms to address such problems. Although genetic algorithms have been proven to facilitate the entire space search, they lack in fine-tuning capability for obtaining the global optimum. Therefore, in this study a hybrid genetic algorithm was developed by integrating both the evolutional and the neighborhood search for permutation optimization.Experimental results of a production scheduling problem indicate that the hybrid genetic algorithm outperforms the other methods, in particular for larger problems. Numerical evidence also shows that different input data from the initial, transient and steady states influence computation efficiency in different ways. Therefore, their properties have been investigated to facilitate the measure of the performance and the estimation of the accuracy.     

Stochastic simulation-based genetic algorithm for chance constraint programming problems with continuous random variables

In this article, we present a stochastic simulation-based genetic algorithm for solving chance constraint programming problems, where the random variables involved in the parameters follow any continuous distribution. Generally, deriving the deterministic equivalent of a chance constraint is very difficult due to complicated multivariate integration and is only possible if the random variables involved in the chance constraint follow some specific distribution such as normal, uniform, exponential and lognormal distribution. In the proposed method, the stochastic model is directly used. The feasibility of the chance constraints are checked using stochastic simulation, and the genetic algorithm is used to obtain the optimal solution. A numerical example is presented to prove the efficiency of the proposed method.     

A hybrid genetic algorithm for constrained multi-objective optimization under uncertainty and target matching problems

This work presents a new approach for interval-based uncertainty analysis. The proposed approach integrates a local search strategy as the worst-case-scenario technique of anti-optimization with a constrained multi-objective genetic algorithm. Anti-optimization is a term for an approach to safety factors in engineering structures which is described as pessimistic and searching for least favorable responses, in combination with optimization techniques but in contrast to probabilistic approaches. The algorithm is applied and evaluated to be efficient and effective in producing good results via target matching problems: a simulated topology and shape optimization problem where a ‘target’ geometry set is predefined as the Pareto optimal solution and a constrained multiobjective optimization problem formulated such that the design solutions will evolve and converge towards the target geometry set.     

Unit commitment problem with ramp rate constraint using a binary-real-coded genetic algorithm

The unit commitment problem (UCP) is a nonlinear mixed-integer optimization problem, encountered as one of the toughest problems in power systems. The problem becomes even more complicated when dynamic power limit based ramp rate constraint is taken into account. Due to the inadequacy of deterministic methods in handling large-size instances of the UCP, various metaheuristics are being considered as alternative algorithms to realistic power systems, among which genetic algorithm (GA) has been investigated widely since long back. Such proposals have been made for solving only the integer part of the UCP, along with some other approaches for the real part of the problem. Moreover, the ramp rate constraint is usually discussed only in the formulation part, without addressing how it could be implemented in an algorithm. In this paper, the GA is revisited with an attempt to solve both the integer and real parts of the UCP using a single algorithm, as well as to incorporate the ramp rate constraint in the proposed algorithm also. In the computational experiment carried out with power systems up to 100 units over 24-h time horizon, available in the literature, the performance of the proposed GA is found quite satisfactory in comparison with the previously reported results.     

Solving a multi-floor layout design model of a dynamic cellular manufacturing system by an efficient genetic algorithm

This paper presents a mixed-integer programming model for a multi-floor layout design of cellular manufacturing systems (CMSs) in a dynamic environment. A novel aspect of this model is to concurrently determine the cell formation (CF) and group layout (GL) as the interrelated decisions involved in the design of a CMS in order to achieve an optimal (or near-optimal) design solution for a multi-floor factory in a multi-period planning horizon. Other design aspects are to design a multi-floor layout to form cells in different floors, a multi-rows layout of equal area facilities in each cell, flexible reconfigurations of cells during successive periods, distance-based material handling cost, and machine depot keeping idle machines. This model incorporates with an extensive coverage of important manufacturing features used in the design of CMSs. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, purchasing machines, machine processing, machine overhead, and machine relocation. Two numerical examples are solved by the CPLEX software to verify the performance of the presented model and illustrate the model features. Since this model belongs to NP-hard class, an efficient genetic algorithm (GA) with a matrix-based chromosome structure is proposed to derive near-optimal solutions. To verify its computational efficiency in comparison to the CPLEX software, several test problems with different sizes and settings are implemented. The efficiency of the proposed GA in terms of the objective function value and computational time is proved by the obtained results.     

Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm

In real life applications we often have the following problem: How to find the reasonable assignment strategy to satisfy the source and destination requirement without shipping goods from any pairs of prohibited sources simultaneously to the same destination so that the total cost can be minimized. This kind of problem is known as the transportation problem with exclusionary side constraint (escTP). Since this problem is one of nonlinear programming models, it is impossible to solve this problem using a traditional linear programming software package (i.e., LINDO). In this paper, an evolutionary algorithm based on a genetic algorithm approach is proposed to solve it. We adopt a Prüfer number to represent the candidate solution to the problem and design the feasibility of the chromosome. Moreover, to handle the infeasible chromosome, here we also propose the repairing procedure. In order to improve the performance of the genetic algorithm, the fuzzy logic controller (FLC) is used to dynamically control the genetic operators. Comparisons with other conventional methods and the spanning tree-based genetic algorithm (st-GA) are presented and the results show the proposed approach to be better as a whole.     

Integrated optimization of inventory-distribution systems by random local search and a genetic algorithm

A new model and its solution procedure for the commodity distribution system consisting of distribution centers and consumer points are discussed. Demand is assumed to be a random variable that obeys a known, stationary probability distribution. An integrated optimization model is built where both the order-up-to-R policy, which is one of the typical inventory policies for periodic review models, and the transportation problem are considered simultaneously. The assignment of consumer points to distribution centers is not fixed. The problem is to determine the target inventory and the transportation quantity in order to minimize the expectation of the sum of inventory related costs and transportation costs. Simulation and linear programming are used to calculate the expected costs, and a random local search method is developed in order to determine the optimum target inventory. A genetic algorithm is also tested and compared with the proposed random local search method. The model and effectiveness of the proposed solution procedure are clarified by computational experiments.     

Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach

We consider the multiprocessor scheduling of unit time tasks with precedence constraints and finite set of limited resources. Each task demands some amount of resources for its execution and the total demand for each kind of resources must not exceed a certain limit at any instant of time. Our objective is to find out the minimum time schedule which satisfies the partial orders and the resource usage constraints. We have applied Genetic Algorithm for the present problem. We have shown that the Genetic Algorithm is quite superior to the First Fit Decreasing method.     

Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm

The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to solve the clustering problem, while a simple heuristic algorithm is formulated to solve the set of traveling salesman problems. The solution of the original problem is obtained through iterative interactions between the main problem and the set of sub-problems. The performance of the proposed approach is compared with the well-known insertion method and a manual scheduling of a distribution center.     

Solving facilities location problem in the presence of alternative processing routes using a genetic algorithm

Facilities location problem deals with the optimization of location of manufacturing facilities like machines, departments, etc. in the shop floor. This problem greatly affects performance of a manufacturing system. It is assumed in this paper that there are multiple products to be produced on several machines. Alternative processing routes are considered for each product and the problem is to determine the processing route of each product and the location of each machine to minimize the total distance traveled by the materials within the shop floor. This paper presents a mixed-integer non-linear mathematical programming formulation to find optimal solution of this problem. A technique is used to linearize the formulated non-linear model. However, due to the NP-hardness of this problem, even the linearized model cannot be optimally solved by the conventional mathematical programming methods in a reasonable time. Therefore, a genetic algorithm is proposed to solve the linearized model. The effectiveness of the GA approach is evaluated with numerical examples. The results show that the proposed GA is both effective and efficient in solving the attempted problem.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems

This paper investigates an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP). By encoding a path as an OST, in contrast with the existing evolutionary algorithms (EA) for shortest path problem (SPP), the designed GA provides a “search from a paths set to another paths set” mutation mechanism such that both of its local search and global search capabilities are greatly improved. Because the possibility to find a feasible path in a paths set is usually larger than that of only one path is feasible, the designed GA has more predominance for solving MCSPPs. Some computational tests are presented and the test results are compared with those obtained by a recent EA of which the encoding approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for shortest path problems. The test results indicate that the new algorithm is available for both of MSPP and MCSPP.     

Haplotype estimation from genotypical data by genetic algorithm

The study of a disease using genetic identification has become possible by using haplotype information. The expectation-maximization algorithms are the standard approach in haplotype analysis. These approaches maximize the likelihood function of a genotypic distribution assuming Hardy-Weinberg equilibrium. However, these methods are time-consuming when applied to the sequence of many loci. In this study, we used a genetic algorithm to obtain the haplotype frequencies from the frequencies of genotypes. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

A permutation-based dual genetic algorithm for dynamic optimization problems

Adaptation to dynamic optimization problems is currently receiving growing interest as one of the most important applications of genetic algorithms. Inspired by dualism and dominance in nature, genetic algorithms with the dualism mechanism have been applied for several dynamic problems with binary encoding. This paper investigates the idea of dualism for combinatorial optimization problems in dynamic environments, which are also extensively implemented in the real-world. A new variation of the GA, called the permutation-based dual genetic algorithm (PBDGA), is presented. Within this GA, two schemes based on the characters of the permutation in group theory are introduced: a partial-dualism scheme motivated by a new multi-attribute dualism mechanism and a learning scheme. Based on the dynamic test environments constructed by stationary benchmark problems, experiments are carried out to validate the proposed PBDGA. The experimental results show the efficiency of PBDGA in dynamic environments.     

Mapping stream programs onto multicore platforms by local search and genetic algorithm

This paper presents a number of novel metaheuristic approaches that can efficiently map stream graphs on multicores. A stream graph consists of a set of actors performing different functions communicating through edges. Orchestrating stream graphs on multicores can be formulated as an Integer Linear Programming (ILP) problem but ILP solver takes exponential time to provide an optimal solution. We propose metaheuristic algorithms to achieve near optimal solutions within a reasonable amount of time. We employ six different variants of the Hill-Climbing (HC) algorithm employing different tweak operators that produce excellent result extremely quickly. We also propose six different variants of Genetic Algorithm (GA) to examine how effective these variants can be in escaping the local optima. We finally combine HC and GA techniques (which is also known as ‘memetic algorithm’) to produce hybrid techniques that outperform the individual performance of HC and GA techniques. We compare our results with the results generated by the CPLEX optimization tool. Our best technique has achieved a geometric mean speedup of 7.42× across a range of StreamIt benchmarks on an eight-core processor.     

Driver fatigue detection using a genetic algorithm

Nowadays, many traffic accidents occur due to driver fatigue. Driver fatigue detection based on computer vision is one of the most hopeful applications of image recognition technology. There are several factors that reflect driver's fatigue. Many efforts have been made to develop fatigue monitoring, but most of them focus on only a single behavior, a feature of the eyes, or a head motion, or mouth motion, etc. When fatigue monitoring is implemented on a real model, it is difficult to predict the driver fatigue accurately or reliably based only on a single driver behavior. Additionally, the changes in a driver's performance are more complicated and not reliable. In this article, we represent a model that simulates a space in a real car. A web camera as a vision sensor is located to acquire video-images of the driver. Three typical characteristics of driver fatigue are involved, pupil shape, eye blinking frequency, and yawn frequency. As the influences of these characteristics on driver fatigue are quite different from each other, we propose a genetic algorithm (GA)-based neural network (NN) system to fuse these three parameters. We use the GA to determine the structure of the neural network system. Finally, simulation results show that the proposed fatigue monitoring system detects driver fatigue probability more exactly and robustly. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

Surface registration using a dynamic genetic algorithm

Robust and fast free-form surface registration is a useful technique in various areas such as object recognition and 3D model reconstruction for animation. Notably, an object model can be constructed, in principle, by surface registration and integration of range images of the target object from different views. In this paper, we propose to formulate the surface registration problem as a high dimensional optimization problem, which can be solved by a genetic algorithm (GA) (Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989). The performance of the GA for surface registration is highly dependent on its speed in evaluating the fitness function. A novel GA with a new fitness function and a new genetic operator is proposed. It can compute an optimal registration 1000 times faster than a conventional GA. The accuracy, speed and the robustness of the proposed method are verified by a number of real experiments.     

Multi-objective reliability optimization for dissimilar-unit cold-standby systems using a genetic algorithm

A genetic algorithm approach is used to solve a multi-objective discrete reliability optimization problem in a k dissimilar-unit non-repairable cold-standby redundant system. Each unit is composed of a number of independent components with generalized Erlang distributions arranged in a series–parallel configuration. There are multiple component choices with different distribution parameters available for being replaced with each component of the system. The objective of the reliability optimization problem is to select the best components, from the set of available components, to be placed in the standby system in order to minimize the initial purchase cost of the system, maximize the system MTTF (mean time to failure), minimize the system VTTF (variance of time to failure) and also maximize the system reliability at the mission time. Finally, we apply a genetic algorithm with double strings using continuous relaxation based on reference solution updating (GADSCRRSU) to solve this multi-objective problem, using goal attainment formulation. The results are also compared against the results of a discrete-time approximation technique to show the efficiency of the proposed GA approach.