A hybrid genetic algorithm for the container loading problem

This paper presents a hybrid genetic algorithm (GA) for the container loading problem with boxes of different sizes and a single container for loading. Generated stowage plans include several vertical layers each containing several boxes. Within the procedure, stowage plans are represented by complex data structures closely related to the problem. To generate offspring, specific genetic operators are used that are based on an integrated greedy heuristic. The process takes several practical constraints into account. Extensive test calculations including procedures from other authors vouch for the good performance of the GA, above all for problems with strongly heterogeneous boxes.     

The choice of screening design

A screening design is an experimental plan used for identifying the expectedly few active factors from potentially many. In this paper, we compare the performances of 3 experimental plans, a Plackett‐Burman design, a minimum run resolution IV design, and a definitive screening design, all with 12 and 13 runs, when they are used for screening and 3 out of 6 factors are active. The functional relationship between the response and the factors was allowed to be of 2 types, a second‐order model and a model with all main effects and interactions included. D‐efficiencies for the designs ability to estimate parameters in such models were computed, but it turned out that these are not very informative for comparing the screening performances of the 2‐level designs to the definitive screening design. The overall screening performance of the 2‐level designs was quite good, but there exist situations where the definitive screening design, allowing both screening and estimation of second‐order models in the same operation, has a reasonable high probability of being successful.     

Aerospace design optimization using a steady state real-coded genetic algorithm

This study demonstrates the advantages of using a real coded genetic algorithm (GA) for aerospace engineering design applications. The GA developed for this study runs steady state, meaning that after every function evaluation the worst performer is determined and that worst performer is then thrown out and replaced by a new member that has been evaluated. The new member is produced by mating two successful parents through a crossover routine, and then mutating that new member. For this study three different preliminary design studies were conducted using both a binary and a real coded GA including a single stage solid propellant missile systems design, a two stage solid propellant missile systems design and a single stage liquid propellant missile systems design.     

Efficient computer experiment-based optimization through variable selection

A computer experiment-based optimization approach employs design of experiments and statistical modeling to represent a complex objective function that can only be evaluated pointwise by running a computer model. In large-scale applications, the number of variables is huge, and direct use of computer experiments would require an exceedingly large experimental design and, consequently, significant computational effort. If a large portion of the variables have little impact on the objective, then there is a need to eliminate these before performing the complete set of computer experiments. This is a variable selection task. The ideal variable selection method for this task should handle unknown nonlinear structure, should be computationally fast, and would be conducted after a small number of computer experiment runs, likely fewer runs (N) than the number of variables (P). Conventional variable selection techniques are based on assumed linear model forms and cannot be applied in this “large P and small N” problem. In this paper, we present a framework that adds a variable selection step prior to computer experiment-based optimization, and we consider data mining methods, using principal components analysis and multiple testing based on false discovery rate, that are appropriate for our variable selection task. An airline fleet assignment case study is used to illustrate our approach.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Analysis of crossovers and selections in a coarse-grained parallel genetic algorithm

The parallel genetic algorithms (PGA) have been developed for combinatorial optimization problems, and its parallel efficiencies have been investigated on a specific problem. These investigations were concerned with how to design a topology and the determination of the optimum setting for parameters (for example, size of subpopulations, migration interval, and so on) rather than the effectiveness of genetic operators. This paper investigates a relation between the parallel efficiency of the coarse-grained PGA and genetic (crossover and selection) operators for the traveling salesman problem on an MIMD parallel computer. The following genetic operators are considered: improved edge recombination (IERX), distance preserving (DPX), and complete subtour exchange (CSEX) crossovers, and two selection operators, which have relatively high selection pressures. Computational results indicate that the parallel efficiency is significantly affected by the difference of crossovers rather than the selections, and the PGA with CSEX gives better properties.     

Multiprogrammering — en orientering

The need for effective utilization of computer facilities has resulted in a great interest in parallel processing of several independent programs on a computer.The introductory parts of this paper deal with multiprogramming both for batch and real-time computer systems. Also some important hardware features such as automatic program interrupts, memory lock-outs and autonomous facilities are discussed.In the following chapter elementary program-mechanics are introduced and attention is paid to priority assignment to different programs.Some main functions of a Master Control Program are then discussed and finally some aspects are given on multiprogram scheduling of computer runs.Multiprogramming is still in an early stage of its development and therefore this paper makes no claim to completeness—it rather attempts to render some important principles of these new techniques.     

Application research on FSDM-based GA in optimizing curriculum schedule model in universities

In this paper, we first analyze the relationship between curricula, teachers, classes, time slices and classrooms in a graph. Then on the basis of constraint conditions in curriculum schedule practically in universities, we presents its optimization model, in which the fuzzy synthetic decision-making (FSDM) is used to optimize genetic algorithm (GA), and a new GA encoding scheme is employed to design fitness and punishment functions for the curriculum schedule problem. This model effectively improved a running performance, which provides a better implementation approach to improvements of the existing curriculum schedule systems. The experimental results show that fitness values of the FSDM-based GA are of obvious evolutional tendency, the chromosome encoding scheme and the fitness function can meet its requirements preferably, and the more adequate computation resources, the greater possibilities of no restoration for the obtained optimal individual.     

Fitting the control parameters of a genetic algorithm: An application to technical trading systems design

This paper studies the problem of how changes in the design of the genetic algorithm (GA) have an effect on the results obtained in real-life applications. In this study, focused on the application of a GA to the tuning of technical trading rules in the context of financial markets, our tentative thesis is that the GA is robust with respect to design changes. The optimization of technical trading systems is a suitable area for the application of the GA metaheuristic, as the complexity of the problem grows exponentially as new technical rules are added to the system and as the answer time is crucial when applying the system to real-time data. Up to now, most of GAs applications to this subject obviated the question of possible “design dependence” in their results. The data we report, based on our experiments, do not allow us to refute the hypothesis of robustness of the GA to design implementation, when applying to technical trading systems tuning.     

Military antenna design using simple and competent genetic algorithms

Over the past decade, the Air Force Research Laboratory (AFRL) Antenna Technology Branch at Hanscom AFB has employed the simple genetic algorithm (SGA) as an optimization tool for a wide variety of antenna applications. Over roughly the same period, researchers at the Illinois Genetic Algorithm Laboratory (IlliGAL) at the University of Illinois at Urbana Champaign have developed GA design theory and advanced GA techniques called competent genetic algorithms—GAs that solve hard problems quickly, reliably, and accurately. Recently, under the guidance and direction of the Air Force Office of Scientific Research (AFOSR), the two laboratories have formed a collaboration, the common goal of which is to apply simple, competent, and hybrid GA techniques to challenging antenna problems.This paper is composed of two parts. The first part of this paper summarizes previous research conducted by AFRL at Hanscom for which SGAs were implemented to obtain acceptable solutions to several antenna problems. This research covers diverse areas of interest, including array pattern synthesis, antenna test-bed design, gain enhancement, electrically small single bent wire elements, and wideband antenna elements.The second part of this paper starts by briefly reviewing the design theory and design principles necessary for the invention and implementation of fast, scalable genetic algorithms. A particular procedure, the hierarchical Bayesian optimization algorithm (hBOA) is then briefly outlined, and the remainder of the paper describes collaborative efforts of AFRL and IlliGAL to solve more difficult antenna problems. In particular, recent results of using hBOA to optimize a novel, wideband overlapped subarray system to achieve −35 dB sidelobes over a 20% bandwidth. The problem was sufficiently difficult that acceptable solutions were not obtained using SGAs. The case study demonstrates the utility of using more advanced GA techniques to obtain acceptable solution quality as problem difficulty increases.     

Generation of efficient frontiers in multi-objective optimization problems by generalized data envelopment analysis

In many practical problems such as engineering design problems, criteria functions cannot be given explicitly in terms of design variables. Under this circumstance, values of criteria functions for given values of design variables are usually obtained by some analyses such as structural analysis, thermodynamical analysis or fluid mechanical analysis. These analyses require considerably much computation time. Therefore, it is not unrealistic to apply existing interactive optimization methods to those problems. On the other hand, there have been many trials using genetic algorithms (GA) for generating efficient frontiers in multi-objective optimization problems. This approach is effective in problems with two or three objective functions. However, these methods cannot usually provide a good approximation to the exact efficient frontiers within a small number of generations in spite of our time limitation. The present paper proposes a method combining generalized data envelopment analysis (GDEA) and GA for generating efficient frontiers in multi-objective optimization problems. GDEA removes dominated design alternatives faster than methods based on only GA. The proposed method can yield desirable efficient frontiers even in non-convex problems as well as convex problems. The effectiveness of the proposed method will be shown through several numerical examples.     

A branch-and-reduce approach to global optimization

This paper presents valid inequalities and range contraction techniques that can be used to reduce the size of the search space of global optimization problems. To demonstrate the algorithmic usefulness of these techniques, we incorporate them within the branch-and-bound framework. This results in a branch-and-reduce global optimization algorithm. A detailed discussion of the algorithm components and theoretical properties are provided. Specialized algorithms for polynomial and multiplicative programs are developed. Extensive computational results are presented for engineering design problems, standard global optimization test problems, univariate polynomial programs, linear multiplicative programs, mixed-integer nonlinear programs and concave quadratic programs. For the problems solved, the computer implementation of the proposed algorithm provides very accurate solutions in modest computational time.     

Solving a large nonlinear programming problem on a vector processing computer

In an earlier paper, the authors formulated an acoustic antenna array design problem as a nonlinear program. Computation times for large problems (about 400 sensors) were in the range of 8 to 10 hours on a Vax 11/780. Most of this time was spent in computing the objective function and its gradient. This paper describes how these computations (and these only) were recoded to exploit the vector processing capabilities of a Cray 1-M computer. Run times are reduced to less than one minute. The results have implications for many nonlinear programs whose function evaluations are very time consuming.     

Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities

The paper presents a simulation–optimization modeling framework for the evacuation of large-scale pedestrian facilities with multiple exit gates. The framework integrates a genetic algorithm (GA) and a microscopic pedestrian simulation–assignment model. The GA searches for the optimal evacuation plan, while the simulation model guides the search through evaluating the quality of the generated evacuation plans. Evacuees are assumed to receive evacuation instructions in terms of the optimal exit gates and evacuation start times. The framework is applied to develop an optimal evacuation plan for a hypothetical crowded exhibition hall. The obtained results show that the model converges to a superior optimal evacuation plan within an acceptable number of iterations. In addition, the obtained evacuation plan outperforms conventional plans that implement nearest-gate immediate evacuation strategies.     

记数抽样检查方案设计与分析软件研制

利用VisualC++6.0Windows开发设计了抽样方案分析与设计软件。软件集成多种功能于一窗口,直观性强,操作方便,计算速度快,不仅可对现行抽样方案检索与分析,而且还可对一次、二次、五次和序贯抽样方案进行设计与分析,并作计算机模拟,可供抽样检查和抽样方案设计人员使用。     

Customized sequential designs for random simulation experiments: Kriging metamodeling and bootstrapping

This paper proposes a novel method to select an experimental design for interpolation in random simulation, especially discrete event simulation. (Though the paper focuses on Kriging, this design approach may also apply to other types of metamodels such as non-linear regression models and splines.) Assuming that simulation requires much computer time, it is important to select a design with a small number of observations (or simulation runs). The proposed method is therefore sequential. Its novelty is that it accounts for the specific input/output behavior (or response function) of the particular simulation at hand; i.e., the method is customized or application-driven. A tool for this customization is bootstrapping, which enables the estimation of the variances of predictions for inputs not yet simulated. The method is tested through two classic simulation models, namely the expected steady-state waiting time of the M/M/1 queuing model, and the mean costs of a terminating (s, S) inventory simulation. For these two simulation models the novel design indeed gives better results than a popular alternative design, namely Latin Hypercube Sampling (LHS) with a prefixed sample.     

Adding more observations to saturated D‐optimal resolution III two‐level factorial designs

We consider the class of saturated main effect plans for the 2^k factorial. With these saturated designs, the overall mean and all main effects can be unbiasedly estimated provided that there are no interactions. However, there is no way to estimate the error variance with such designs. Because of this and other reasons, we like to add some additional runs to the set of (k+1) runs in the D‐optimal design in this class. Our goals here are: (1) to search for s additional runs so that the resulting design based on (k+s+1) runs yields a D‐optimal design in the class of augmented designs; (2) to classify all the runs into equivalent classes so that the runs in the same equivalent class give us the same value of the determinant of the information matrix. This allows us to trade runs for runs if this becomes necessary; (3) to obtain upper bounds for determinant of the information matrices of augmented designs. In this article we shall address these approaches and present some new results. © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 51–77, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10026     

A CASE STUDY IN THE APPLICATION OF SUPERSATURATED DESIGNS TO COMPUTER EXPERIMENTS

Supersaturated design is essentially a fractional factorial design in which the number of potential effects is greater than the number of runs. In this article, the supersaturated design is applied to a computer experiment through an example of steady current circuit model problem. A uniform mixed-level supersaturated design and the centered quadratic regression model are used. This example shows that supersaturated design and quadratic regression modeling method are very effective for screening effects and building the predictor. They are not only useful in computer experiments but also in industrial and other scientific experiments.     

Calibrating continuous multi-objective heuristics using mixture experiments

A genetic algorithm heuristic that uses multiple rank indicators taken from a number of well established evolutionary algorithms including NSGA-II, IBEA and SPEA2 is developed. It is named Multi-Indicator GA (MIGA). At every iteration, MIGA uses one among the available indicators to select the individuals which will participate as parents in the next iteration. MIGA chooses the indicators according to predefined probabilities found through the analysis of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the point that provides the maximum we also find good algorithm parameters. To the best of our knowledge, this is the first paper where mixture experiments are used for heuristic tuning. The design of mixture experiments approach allowed the authors to identify and exploit synergy between the different rank indicators. This is demonstrated by our experimental results in which the tuned MIGA compares favorably to other well established algorithms, an uncalibrated multi-indicator algorithm, and a multi-indicator algorithm calibrated using a more conventional approach.     

Computational study of a nonhierarchical decomposition algorithm

Optimizing the design of complex ground and flight vehicles involves multiple disciplines and multilayered computer codes stitched together from mostly incompativle disciplinary codes. The application of established, large-scale, optimization algorithms to the complete model is nearly impossible. Hierarchical decompositions are inappropriate for these types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategyfor nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two-dimensional quadratic programs. This paper demonstrates the failure of the algorithm for quadratic programs and suggests a number of possible modifications.