基于不可行度和内分泌原理的多目标粒子群方法

针对有约束条件的多目标优化问题,提出了一种求解带约束的基于内分泌思想的多目标粒子群算法。利用不可行度方法和约束主导原理指导进化过程中精英种群的选择操作和约束条件的处理,根据生物体激素调节机制中促激素和释放激素间的相互作用原理,考虑当前非劣解集中的个体对其最邻近的一类群体的监督控制,引入当前粒子的类全局最优位置来反映其所属类中最好位置粒子对当前粒子的影响。为验证多目标约束优化算法的有效性,对两个典型的多目标优化问题进行了仿真实验,仿真结果表明该算法能较大概率地获得多目标约束优化问题的可行Pareto最优解。     

Constraint handling in genetic algorithms using a gradient-based repair method

Constraint handling is one of the major concerns when applying genetic algorithms (GAs) to solve constrained optimization problems. This paper proposes to use the gradient information derived from the constraint set to systematically repair infeasible solutions. The proposed repair procedure is embedded into a simple GA as a special operator. Experiments using 11 benchmark problems are presented and compared with the best known solutions reported in the literature. Our results are competitive, if not better, compared to the results reported using the homomorphous mapping method, the stochastic ranking method, and the self-adaptive fitness formulation method.     

Where Are the Niches? Dynamic Fitness Sharing

The problem of locating all the optima within a multimodal fitness landscape has been widely addressed in evolutionary computation, and many solutions, based on a large variety of different techniques, have been proposed in the literature. Among them, fitness sharing (FS) is probably the best known and the most widely used. The main criticisms to FS concern both the lack of an explicit mechanism for identifying or providing any information about the location of the peaks in the fitness landscape, and the definition of species implicitly assumed by FS. We present a mechanism of FS, i.e., dynamic fitness sharing, which has been devised in order to overcome these limitations. The proposed method allows an explicit, dynamic identification of the species discovered at each generation, their localization on the fitness landscape, the application of the sharing mechanism to each species separately, and a species elitist strategy. The proposed method has been tested on a set of standard functions largely adopted in the literature to assess the performance of evolutionary algorithms on multimodal functions. Experimental results confirm that our method performs significantly better than FS and other methods proposed in the literature without requiring any further assumption on the fitness landscape than those assumed by the FS itself.     

An iterative local search approach based on fitness landscapes analysis for the delay-constrained multicast routing problem

This paper presents the first fitness landscape analysis on the delay-constrained least-cost multicast routing problem (DCLC-MRP). Although the problem has attracted an increasing research attention over the past decade in telecommunications and operational research, little research has been conducted to analyze the features of its underlying landscape. Two of the most commonly used landscape analysis techniques, the fitness distance correlation analysis and the autocorrelation analysis, have been applied to analyze the global and local landscape features of DCLC-MRPs. A large amount of simulation experiments on a set of problem instances generated based on the benchmark Steiner tree problems in the OR-library reveals that the landscape of the DCLC-MRP is highly instance dependent with different landscape features. Different delay bounds also affect the distribution of solutions in the search space. The autocorrelation analysis on the benchmark instances of different sizes and delay bounds shows the impact of different local search heuristics and neighborhood structures on the fitness distance landscapes of the DCLC-MRP. The delay bound constraint in the DCLC-MRP has shown a great influence on the underlying landscape characteristic of the problem. Based on the fitness landscape analysis, an iterative local search (ILS) approach is proposed in this paper for the first time to tackle the DCLC-MRP. Computational results demonstrate the effectiveness of the proposed ILS algorithm for the problem in comparison with other algorithms in the literature.     

一种求解约束优化问题的遗传算法

提出一种求解约束优化问题的遗传算法。通过可行解与不可行解算术交叉的方法对问题的决策空间进行搜索,对可行种群和不可行种群分别按照适应度和约束违反度进行选择。传统变异操作使得解往往偏离了约束区域,因此引入对可行解的边界变异和对不可行解的非均匀变异,并通过维变异方法保持种群的多样性。数值实验结果说明该算法的有效性。     

Surrogate modeling based on an adaptive network and granular computing

Reducing the number of evaluations of expensive fitness functions is one of the main concerns in evolutionary algorithms, especially when working with instances of contemporary engineering problems. As an alternative to this efficiency constraint, surrogate-based methods are grounded in the construction of approximate models that estimate the solutions’ fitness by modeling the relationships between solution variables and their performance. This paper proposes a methodology based on granular computing for the construction of surrogate models for evolutionary algorithms. Under the proposed method, granules are associated with representative solutions of the problem under analysis. New solutions are evaluated with the expensive (original) fitness function only if they are not already covered by an existing granule. The parameters defining granules are periodically adapted as the search goes on using a neuro-fuzzy network that does not only reduce the number of fitness function evaluations, but also provides better convergence capabilities. The proposed method is evaluated on classical benchmark functions and on a recent benchmark created to test large-scale optimization models. Our results show that the proposed method considerably reduces the actual number of fitness function evaluations without significantly degrading the quality of solutions.     

An alternative simple solution algorithm of an inventory model with fixed and variable lead time crash costs under unknown demand distribution

Inventory models with controllable lead time both for known and unknown demand distributions have been proposed in the literature. A model is useless unless it is formulated correctly and feasible. A simple solution procedure of a model also plays an important role in its application. This article highlights an erroneous formulation of an inventory model developed with fixed and variable lead time crash costs under unknown demand distribution, and also demonstrates its infeasibility. To attain feasibility we extend the model to include a constraint. Then, we present an alternative simple solution technique of the modified model and carry out a comparative study on a numerical example to show its potential significance.     

Evolution of Fuzzy Controllers for Robotic Vehicles: The Role of Fitness Function Selection

An important issue not addressed in the literature, is related to the selection of the fitness function parameters which are used in the evolution process of fuzzy logic controllers for mobile robot navigation. The majority of the fitness functions used for controllers evolution are empirically selected and (most of times) task specified. This results to controllers which heavily depend on fitness function selection. In this paper we compare three major different types of fitness functions and how they affect the navigation performance of a fuzzy logic controlled real robot. Genetic algorithms are employed to evolve the membership functions of these controllers. Further, an efficiency measure is introduced for the systematic analysis and benchmarking of overall performance. This measure takes into account important performance results of the robot during experimentation, such as the final distance from target, the time needed to reach its final position, the time of sensor activation, the mean linear velocity e.t.c. In order to examine the validity of our approach a low cost mobile robot has been developed, which is used as a testbed.     

An infeasible active-set QP-free algorithm for general nonlinear programming

We propose an infeasible active set QP-free algorithm for general constrained optimization in this paper. It starts from an arbitrary initial point. At each iteration, only two or three reduced linear equations with the same coefficients are solved to obtain the search direction. To determine the working set, the method makes use of multipliers from the last iteration, eliminating the need to compute a new estimate, and no additional linear systems are solved to select linear independent constraint gradients. The infeasibility measure and the objective function value are controlled separately by the filter technique. Without the positive definiteness assumption on the Hessian estimate, the sequence generated by the algorithm still globally converges to a Karush-Kuhn-Tucker point. And the algorithm obtains superlinear convergence without the strict complementarity. At last, preliminary numerical results are reported.     

A modified super-efficiency measure based on simultaneous input–output projection in data envelopment analysis

Super-efficiency data envelopment analysis (SE-DEA) models have been developed and applied in many situations. However, under the condition of variable returns to scale (VRS), infeasibility of the SE-DEA model may occur and restrict its application. A modified SE-DEA measure based on simultaneous input–output projection is proposed as a way to systematically characterize the super-efficiency in both inputs and outputs. The modified measure overcomes the infeasibility problem while providing ease of computation and interpretation. The practicability of the proposed measure in real applications and its comparison to other super-efficiency measures are illustrated empirically using an example.     

Genetic algorithms optimization for normalized normal constraint method under Pareto construction

This paper presents the resolution of multiobjective optimization problems as a tool in engineering design. In the literature, the solutions of this problems are based on the Pareto frontier construction. Therefore, substantial efforts have been made in recent years to develop methods for the construction of Pareto frontiers that guarantee uniform distribution and exclude the non-Pareto and local Pareto points. The normalized normal constraint is a recent contribution that generates a well-distributed Pareto frontier. Nevertheless, these methods are susceptible of improvement or modifications to obtain the same level of results more efficiently. This paper proposes a modification of the original normalized normal constraint method using a genetic algorithms in the optimization task. The results presented in this paper show a suitable behavior for the genetic algorithms method compared to classical Gauss–Newton optimization methods which are used by the original normalized normal constraint method.     

Reliability analysis of the rank transform for stereo matching

The rank transform is a nonparametric technique which has been recently proposed for the stereo matching problem. The motivation behind its application to this problem is its invariance to certain types of image distortion and noise, as well as its amenability to real-time implementation. This paper derives one constraint which must be satisfied for a correct match. This has been termed the rank constraint. Experimental work has shown that this constraint is capable of resolving ambiguous matches, thereby improving matching reliability. A novel matching algorithm incorporating the rank constraint has also been proposed. This modified algorithm consistently resulted in an increased percentage of correct matches, for all test imagery used. Furthermore, the rank constraint has been used to devise a method of identifying regions of an image where the rank transform, and hence matching outcome, is more susceptible to noise. Experimental results have shown that the errors predicted using this technique are consistent with the actual errors which result when images are corrupted with noise. Such a method could be used to identify matches which are likely to be incorrect and/or provide a measure of confidence in a match.     

A modified distance method for multicriteria optimization, using genetic algorithms

The common application areas of Genetic Algorithms (GAs) have been to single criterion difficult optimization problems. The GA selection mechanism is often dependent upon a single valued scalar objective funtion. In this paper, we present results of a modified distance method. The distance method was proposed earlier by us, for solving multiple criteria problems with GAs. The Pareto set estimation method, which is fundamental to multicriteria analysis, is used to perform the multicriteria optimization using GAs. First, the Pareto set is found out from the population of the initial generation of the GA. The fitness of a new solution, is calculated by a distance measure with reference to the Pareto set of the previous runs. We calculate the distances of a solution from all the Pareto solutions found since the previous run, but the minimum of these distances is taken under consideration while evaluating the fitness of the solution. Thus the GA tries to maximize the distance of future Pareto solutions from present Pareto solutions in the positive Pareto space of the given problem. Here we modify distance method, by using an improved algorithm to assign and make use of the latent potential of the Pareto solutions which are found during the runs. Two detailed numerical examples and computer generated results are also presented.     

Adaptive memory search for multidemand multidimensional knapsack problems

We describe a simple adaptive memory search method for the 0/1 Multidemand Multidimensional Knapsack Problem (0/1 MDMKP). The search balances the level of infeasibility against the quality of the solution, and uses a simple dynamic tabu search mechanism. A weighting scheme to balance out the differences in the tightness of the constraints is also implemented. Computational results on a portfolio of test problems taken from the literature are reported, showing very favorable results, both in terms of solution quality and the ability of the search to find feasible solutions.     

Meta-modeling using generalized regression neural network and particle swarm optimization

Swarm intelligence (SI) and evolutionary computation (EC) algorithms are often used to solve various optimization problems. SI and EC algorithms generally require a large number of fitness function evaluations (i.e., higher computational requirements) to obtain quality solutions. This requirement becomes more challenging when optimization problems are associated with computationally expensive analyses and/or simulation tasks. To tackle this issue, meta-modeling has shown successful results in improving computational efficiency by approximating the fitness or constraint functions of these complex optimization problems. Meta-modeling approaches typically use polynomial regression, kriging, radial basis function network, and support vector machines. Less attention has been given to the generalized regression neural network approach, and yet, it offers several advantages. Specifically, the model construction process does not require iterations. Its only one parameter is known to be less sensitive and usually requires less effort in selecting an optimal parameter. We use generalized regression neural network in this paper to construct meta-models and to approximate the fitness function in particle swarm optimization. To assess the performance and quality of these solutions, the proposed meta-modeling approach is tested on ten benchmark functions. The results are promising in terms of the solution quality and computational efficiency, especially when compared against the results of particle swarm optimization without meta-modeling and several other meta-modeling methods in previously published literature.     

Infeasibility handling in genetic algorithm using nested domains for production planning

In this paper we present a genetic algorithm with new components to tackle capacitated lot sizing and scheduling problems with sequence dependent setups that appear in a wide range of industries, from soft drink bottling to food manufacturing.Finding a feasible solution to highly constrained problems is often a very difficult task. Various strategies have been applied to deal with infeasible solutions throughout the search. We propose a new scheme of classifying individuals based on nested domains to determine the solutions according to the level of infeasibility, which in our case represents bands of additional production hours (overtime). Within each band, individuals are just differentiated by their fitness function. As iterations are conducted, the widths of the bands are dynamically adjusted to improve the convergence of the individuals into the feasible domain.The numerical experiments on highly capacitated instances show the effectiveness of this computational tractable approach to guide the search toward the feasible domain. Our approach outperforms other state-of-the-art approaches and commercial solvers.     

基于局部搜索与混合多样性策略的多目标粒子群算法

为了提高算法的收敛性与非支配解集的多样性,提出一种基于局部搜索与混合多样性策略的多目标粒子群算法（LH-MOPSO）.该算法使用增广Lagrange乘子法对非支配解进行局部搜索以快速接近Pareto最优解;利用基于改进的Maximin适应值函数与拥挤距离的混合多样性策略对非支配解集进行维护以保留解的多样性,同时引入高斯变异算子以避免算法早熟收敛;最后针对多目标约束优化问题,给出一种有效的约束处理方法.实验研究表明该算法具有良好的优化性能.     

A problem space genetic algorithm in multiobjective optimization

In this study, a problem space genetic algorithm (PSGA) is used to solve bicriteria tool management and scheduling problems simultaneously in flexible manufacturing systems. The PSGA is used to generate approximately efficient solutions minimizing both the manufacturing cost and total weighted tardiness. This is the first implementation of PSGA to solve a multiobjective optimization problem (MOP). In multiobjective search, the key issues are guiding the search towards the global Pareto-optimal set and maintaining diversity. A new fitness assignment method, which is used in PSGA, is proposed to find a well-diversified, uniformly distributed set of solutions that are close to the global Pareto set. The proposed fitness assignment method is a combination of a nondominated sorting based method which is most commonly used in multiobjective optimization literature and aggregation of objectives method which is popular in the operations research literature. The quality of the Pareto-optimal set is evaluated by using the performance measures developed for multiobjective optimization problems.     

Constraints Satisfaction through Recursive Neural Networks with Mixed Penalties: a Case Study

This paper investigates an industrial assignment problem. It is modelized as a constraint satisfaction problem of large size with linear inequalities and binary variables. A new analog neuron-like network is proposed to find out feasible solutions to problems having several thousands of 0/1 variables. The approach developed in this paper is based on mixed-penalty functions: exterior penalty functions together with interior penalty functions. Starting from a near-binary solution satisfying each linear inequality, the network generates trial solutions located outside or inside the feasible set, in order to minimize an energy function which measures the total binary infeasibility of the system. The performances of the network are demonstrated on real data sets.