Simulation optimization with qualitative variables and structural model changes: A genetic algorithm approach

In many common simulation optimization methods the structure of the system stays the same and only the set of values for certain parameters of the system such as the number of machines in a station or the in-process inventory is varied from one evaluation to the next. The methodology described in this paper is a simulation-optimization process where the qualitative variables and the structure of the system are the subjects of optimization. Here, the optimum response sought is a function of design and operation characteristics of the system such as the type of machines to use, dispatching rules, sequence of processing operations, etc. In the methodology developed here simulation models are automatically generated through an object-oriented process and are evaluated for various candidate configurations of the system. These candidates are suggested by a Genetic Algorithm (GA) that automatically guides the system towards better solutions. After simulating the alternatives, the results are returned to the GA to be utilized in selection of the next generation of configurations to be evaluated. This process continues until a satisfactory solution is obtained for the system.     

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

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

Selecting survivors in genetic algorithm using tabu search strategies

Genetic algorithm (GA) is well-known for its effectiveness in global search and optimization. To balance selection pressure and population diversity is an important issue of designing GA. This paper proposes a novel hybridization of GA and tabu search (TS) to address this issue. The proposed method embeds the key elements of TS—tabu restriction and aspiration criterion—into the survival selection operator of GA. More specifically, the tabu restriction is used to prevent inbreeding for diversity maintenance, and the aspiration criterion is activated to provide moderate selection pressure under the tabu restriction. The interaction of tabu restriction and aspiration criterion enables survivor selection to balance selection pressure and population diversity. The experimental results on numerical and combinatorial optimization problems show that this hybridization can significantly improve GAs in terms of solution quality as well as convergence speed. An empirical analysis further identifies the influences of the TS strategies on the performance of this hybrid GA.     

Reliability stochastic optimization for a series system with interval component reliability via genetic algorithm

This paper deals with chance constraints based reliability stochastic optimization problem in the series system. This problem can be formulated as a nonlinear integer programming problem of maximizing the overall system reliability under chance constraints due to resources. The assumption of traditional reliability optimization problem is that the reliability of a component is known as a fixed quantity which lies in the open interval (0, 1). However, in real life situations, the reliability of an individual component may vary due to some realistic factors and it is sensible to treat this as a positive imprecise number and this imprecise number is represented by an interval valued number. In this work, we have formulated the reliability optimization problem as a chance constraints based reliability stochastic optimization problem with interval valued reliabilities of components. Then, the chance constraints of the problem are converted into the equivalent deterministic form. The transformed problem has been formulated as an unconstrained integer programming problem with interval coefficients by Big-M penalty technique. Then to solve this problem, we have developed a real coded genetic algorithm (GA) for integer variables with tournament selection, uniform crossover and one-neighborhood mutation. To illustrate the model two numerical examples have been solved by our developed GA. Finally to study the stability of our developed GA with respect to the different GA parameters, sensitivity analyses have been done graphically.     

Fuzzy criteria for feature selection

The presence of less relevant or highly correlated features often decrease classification accuracy. Feature selection in which most informative variables are selected for model generation is an important step in data-driven modeling. In feature selection, one often tries to satisfy multiple criteria such as feature discriminating power, model performance or subset cardinality. Therefore, a multi-objective formulation of the feature selection problem is more appropriate. In this paper, we propose to use fuzzy criteria in feature selection by using a fuzzy decision making framework. This formulation allows for a more flexible definition of the goals in feature selection, and avoids the problem of weighting different goals is classical multi-objective optimization. The optimization problem is solved using an ant colony optimization algorithm proposed in our previous work. We illustrate the added value of the approach by applying our proposed fuzzy feature selection algorithm to eight benchmark problems.     

A hybrid framework for optimizing beam angles in radiation therapy planning

The purpose of this paper is twofold: (1) to examine strengths and weaknesses of recently developed optimization methods for selecting radiation treatment beam angles and (2) to propose a simple and easy-to-use hybrid framework that overcomes some of the weaknesses observed with these methods. Six optimization methods—branch and bound (BB), simulated annealing (SA), genetic algorithms (GA), nested partitions (NP), branch and prune (BP), and local neighborhood search (LNS)—were evaluated. Our preliminary test results revealed that (1) one of the major drawbacks of the reported algorithms was the limited ability to find a good solution within a reasonable amount of time in a clinical setting, (2) all heuristic methods require selecting appropriate parameter values, which is a difficult chore, and (3) the LNS algorithm has the ability to identify good solutions only if provided with a good starting point. On the basis of these findings, we propose a unified beam angle selection framework that, through two sequential phases, consistently finds clinically relevant locally optimal solutions. Considering that different users may use different optimization approaches among those mentioned above, the first phase aims to quickly find a good feasible solution using SA, GA, NP, or BP. This solution is then used as a starting point for LNS to find a locally optimal solution. Experimental results using this unified method on five clinical cases show that it not only produces consistently good-quality treatment solutions but also alleviates the effort of selecting an initial set of appropriate parameter values that is required by all of the existing optimization methods.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

Annealing a Genetic Algorithm for Constrained Optimization

In this paper, we adapt a genetic algorithm for constrained optimization problems. We use a dynamic penalty approach along with some form of annealing, thus forcing the search to concentrate on feasible solutions as the algorithm progresses. We suggest two different general-purpose methods for guaranteeing convergence to a globally optimal (feasible) solution, neither of which makes any assumptions on the structure of the optimization problem. The former involves modifying the GA evolution operators to yield a Boltzmann-type distribution on populations. The latter incorporates a dynamic penalty along with a slow annealing of acceptance probabilities. We prove that, with probability one, both of these methods will converge to a globally optimal feasible state.     

Gbest-guided artificial bee colony algorithm for numerical function optimization

Artificial bee colony (ABC) algorithm invented recently by Karaboga is a biological-inspired optimization algorithm, which has been shown to be competitive with some conventional biological-inspired algorithms, such as genetic algorithm (GA), differential evolution (DE) and particle swarm optimization (PSO). However, there is still an insufficiency in ABC algorithm regarding its solution search equation, which is good at exploration but poor at exploitation. Inspired by PSO, we propose an improved ABC algorithm called gbest-guided ABC (GABC) algorithm by incorporating the information of global best (gbest) solution into the solution search equation to improve the exploitation. The experimental results tested on a set of numerical benchmark functions show that GABC algorithm can outperform ABC algorithm in most of the experiments.     

A Case Study of Stochastic Optimization in Health Policy: Problem Formulation and Preliminary Results

We use Bayesian decision theory to address a variable selection problem arising in attempts to indirectly measure the quality of hospital care, by comparing observed mortality rates to expected values based on patient sickness at admission. Our method weighs data collection costs against predictive accuracy to find an optimal subset of the available admission sickness variables. The approach involves maximizing expected utility across possible subsets, using Monte Carlo methods based on random division of the available data into N modeling and validation splits to approximate the expectation. After exploring the geometry of the solution space, we compare a variety of stochastic optimization methods –- including genetic algorithms (GA), simulated annealing (SA), tabu search (TS), threshold acceptance (TA), and messy simulated annealing (MSA) –- on their performance in finding good subsets of variables, and we clarify the role of N in the optimization. Preliminary results indicate that TS is somewhat better than TA and SA in this problem, with MSA and GA well behind the other three methods. Sensitivity analysis reveals broad stability of our conclusions.     

阶梯状黄土边坡稳定性分析的改进遗传算法及应用

阶梯状黄土边坡稳定性分析的关键是估算其稳定系数的最小值.稳定系数的求解涉及诸多因素且计算过程繁杂,传统优化算法往往不能有效地搜索到其全局最小解.为此,提出一种改进的自适应遗传算法.算法对基因变量空间进行网格状划分,采用迭代选优法建立均匀分布的初始种群,运用优质个体保留遗传策略,并按照特定的准则自适应地调整交叉概率和变异概率,提高算法的全局搜索能力和收敛速度.实例应用表明算法能够快速有效地收敛于土坡稳定系数的全局最小解,且计算结果与实际情况更加吻合.     

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.     

Utilizing expected improvement and generalized data envelopment analysis in multi-objective genetic algorithms

Meta-heuristic methods such as genetic algorithms (GA) and particle swarm optimization (PSO) have been extended to multi-objective optimization problems, and have been observed to be useful for finding good approximate Pareto optimal solutions. In order to improve the convergence and the diversity in the search of solutions using meta-heuristic methods, this paper suggests a new method to make offspring by utilizing the expected improvement (EI) and generalized data envelopment analysis (GDEA). In addition, the effectiveness of the proposed method will be investigated through several numerical examples in comparison with the conventional multi-objective GA and PSO methods.     

A new multi objective optimization approach in distribution systems

This paper presents a multi objective optimal location of AVRs in distribution systems at the presence of distributed generators based on modified teaching-learning-based optimization (MTLBO) algorithm. In the proposed MTLBO algorithm, teacher and learner phases are modified. The proposed objective functions are energy generation costs, electrical energy losses and the voltage deviations. The proposed algorithm utilizes several teachers and considers the teachers as an external repository to save found Pareto optimal solutions during the search process. Since the objective functions are not the same, a fuzzy clustering method is used to control the size of the repository. The proposed technique allows the decision maker to select one of the Pareto optimal solutions (by trade-off) for different applications. The performance of the suggested algorithm on a 70-bus distribution network in comparison with other evolutionary methods such as GA, PSO and TLBO, is extraordinary.     

On a Feasible–Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch

We explore data-driven methods for gaining insight into the dynamics of a two-population genetic algorithm (GA), which has been effective in tests on constrained optimization problems. We track and compare one population of feasible solutions and another population of infeasible solutions. Feasible solutions are selected and bred to improve their objective function values. Infeasible solutions are selected and bred to reduce their constraint violations. Interbreeding between populations is completely indirect, that is, only through their offspring that happen to migrate to the other population. We introduce an empirical measure of distance, and apply it between individuals and between population centroids to monitor the progress of evolution. We find that the centroids of the two populations approach each other and stabilize. This is a valuable characterization of convergence. We find the infeasible population influences, and sometimes dominates, the genetic material of the optimum solution. Since the infeasible population is not evaluated by the objective function, it is free to explore boundary regions, where the optimum is likely to be found. Roughly speaking, the No Free Lunch theorems for optimization show that all blackbox algorithms (such as Genetic Algorithms) have the same average performance over the set of all problems. As such, our algorithm would, on average, be no better than random search or any other blackbox search method. However, we provide two general theorems that give conditions that render null the No Free Lunch results for the constrained optimization problem class we study. The approach taken here thereby escapes the No Free Lunch implications, per se.     

Optimal design of a 2 DOF parallel robot

This paper is aimed at presenting a study on the optimization of the Biglide mini parallel robot, which comprises two-degree-of-freedom (DOF) mini parallel robots with constant struts. The robot workspace is characterized and the inverse kinematics equation is obtained. In the paper, design optimization is implemented with Genetic Algorithms (GA) for optimization considering transmission quality index and workspace. Here, intended to show the advantages of using the GA, we applied it to a multicriteria optimization problem of 2 DOF mini parallel robot. Genetic algorithms (GA) are so far generally the best and most robust kind of evolutionary algorithms. A GA has a number of advantages. It can quickly scan a vast solution set. Bad proposals do not affect the end solution negatively as they are simply discarded. The obtained results have shown that the use of GA in such kind of optimization problem enhances the quality of the optimization outcome, providing a better and more realistic support for the decision maker. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimal selection of retailers for a manufacturing vendor in a vendor managed inventory system

A Vendor Managed Inventory (VMI) system consists of a manufacturing vendor and a number of retailers. In such a system, it is essential for the vendor to optimally determine retailer selection and other related decisions, such as the product’s replenishment cycle time and the wholesale price, in order to maximize his profit. Meanwhile, each retailer’s decisions on her willingness to enter the system and retail price are simultaneously considered in the retailer selection process. However, the above interactive decision making is complex and the available studies on interactive retailer selection are scarce. In this study, we formulate the retailer selection problem as a Stackelberg game model to help the manufacturer, as a vendor, optimally select his retailers to form a VMI system. This model is non-linear, mixed-integer, game-theoretic, and analytically intractable. Therefore, we further develop a hybrid algorithm for effectively and efficiently solving the developed model. The hybrid algorithm combines dynamic programming (DP), genetic algorithm (GA) and analytical methods. As demonstrated by our numerical studies, the optimal retailer selection can increase the manufacturer’s profit by up to 90% and the selected retailers’ profits significantly compared to non-selection strategy. The proposed hybrid algorithm can solve the model within a minute for a problem with 100 candidate retailers, whereas a pure GA has to take more than 1 h to solve a small sized problem of 20 candidate retailers achieving an objective value no worse than that obtained by the hybrid algorithm.     

Flying-V型仓储布局货位分配优化方法研究

Flying-V是一种典型的非传统布局方式,根据其布局方式的特性,针对仓储货位分配优化问题,以货物出入库效率最高和货物存放的重心最低为优化目标,建立了货位分配多目标优化模型,并采用自适应策略的遗传算法(GA),以及粒子群算法(PSO)进行求解。根据货位分配的优化特点,在GA算法的选择、交叉和变异环节均采用自适应策略, 同时采用惯性权重线性递减的方法设计了PSO算法,有效地解决了两种算法收敛速度慢和易“早熟”的问题,提高了算法的寻优性能。为了更好地表现两种优化求解算法的有效性和优越性,结合具体的货位分配实例利用MATLAB软件编程实现。通过对比分析优化结果表明,PSO算法在收敛速度和优化效果方面相比于自适应GA算法更具有优势,更加合适于解决Flying-V型仓储布局货位分配优化问题。     

Reducing the bandwidth of a sparse matrix with a genetic algorithm

Abstract

The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.     

Particle swarm optimization: Hybridization perspectives and experimental illustrations

Metaheuristic optimization algorithms have become popular choice for solving complex and intricate problems which are otherwise difficult to solve by traditional methods. In the present study an attempt is made to review the hybrid optimization techniques in which one main algorithm is a well known metaheuristic; particle swarm optimization or PSO. Hybridization is a method of combining two (or more) techniques in a judicious manner such that the resulting algorithm contains the positive features of both (or all) the algorithms. Depending on the algorithm/s used we made three classifications as (i) Hybridization of PSO and genetic algorithms (ii) Hybridization of PSO with differential evolution and (iii) Hybridization of PSO with other techniques. Where, other techniques include various local and global search methods. Besides giving the review we also show a comparison of three hybrid PSO algorithms; hybrid differential evolution particle swarm optimization (DE-PSO), adaptive mutation particle swarm optimization (AMPSO) and hybrid genetic algorithm particle swarm optimization (GA-PSO) on a test suite of nine conventional benchmark problems.