An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls

This paper presents a preference-based method to handle optimization problems with multiple objectives. With an increase in the number of objectives the computational cost in solving a multi-objective optimization problem rises exponentially, and it becomes increasingly difficult for evolutionary multi-objective techniques to produce the entire Pareto-optimal front. In this paper, an evolutionary multi-objective procedure is combined with preference information from the decision maker during the intermediate stages of the algorithm leading to the most preferred point. The proposed approach is different from the existing approaches, as it tries to find the most preferred point with a limited budget of decision maker calls. In this paper, we incorporate the idea into a progressively interactive technique based on polyhedral cones. The idea is also tested on another progressively interactive approach based on value functions. Results are provided on two to five-objective unconstrained as well as constrained test problems.     

Interactive evolutionary multi-objective optimization for quasi-concave preference functions

We present a new hybrid approach to interactive evolutionary multi-objective optimization that uses a partial preference order to act as the fitness function in a customized genetic algorithm. We periodically send solutions to the decision maker (DM) for her evaluation and use the resulting preference information to form preference cones consisting of inferior solutions. The cones allow us to implicitly rank solutions that the DM has not considered. This technique avoids assuming an exact form for the preference function, but does assume that the preference function is quasi-concave. This paper describes the genetic algorithm and demonstrates its performance on the multi-objective knapsack problem.     

自适应多种群回溯群居蜘蛛算法求解TSP问题

在群居蜘蛛优化算法中引入自适应决策半径,将蜘蛛种群动态地分成多个种群,种群内适应度不同的个体采取不同的更新方式.在筛选全局极值的基础上,根据进化程度执行回溯迭代更新,提出一种自适应多种群回溯群居蜘蛛优化算法,旨在提高种群样本多样性和算法全局寻优能力.函数寻优结果表明改进算法具有较快的收敛速度和较高的收敛精度.最后将其应用于TSP问题的求解.     

Constrained optimization using multiple objective programming

In practical applications of mathematical programming it is frequently observed that the decision maker prefers apparently suboptimal solutions. A natural explanation for this phenomenon is that the applied mathematical model was not sufficiently realistic and did not fully represent all the decision makers criteria and constraints. Since multicriteria optimization approaches are specifically designed to incorporate such complex preference structures, they gain more and more importance in application areas as, for example, engineering design and capital budgeting. The aim of this paper is to analyze optimization problems both from a constrained programming and a multicriteria programming perspective. It is shown that both formulations share important properties, and that many classical solution approaches have correspondences in the respective models. The analysis naturally leads to a discussion of the applicability of some recent approximation techniques for multicriteria programming problems for the approximation of optimal solutions and of Lagrange multipliers in convex constrained programming. Convergence results are proven for convex and nonconvex problems.     

New interval methods for constrained global optimization

Interval analysis is a powerful tool which allows to design branch-and-bound algorithms able to solve many global optimization problems. In this paper we present new adaptive multisection rules which enable the algorithm to choose the proper multisection type depending on simple heuristic decision rules. Moreover, for the selection of the next box to be subdivided, we investigate new criteria. Both the adaptive multisection and the subinterval selection rules seem to be specially suitable for being used in inequality constrained global optimization problems. The usefulness of these new techniques is shown by computational studies.     

Local models—an approach to distributed multi-objective optimization

When solving real-world optimization problems, evolutionary algorithms often require a large number of fitness evaluations in order to converge to the global optima. Attempts have been made to find techniques to reduce the number of fitness function evaluations. We propose a novel framework in the context of multi-objective optimization where fitness evaluations are distributed by creating a limited number of adaptive spheres spanning the search space. These spheres move towards the global Pareto front as components of a swarm optimization system. We call this process localization. The contribution of the paper is a general framework for distributed evolutionary multi-objective optimization, in which the individuals in each sphere can be controlled by any existing evolutionary multi-objective optimization algorithm in the literature.     

A Single Component Mutation Evolutionary Programming

In this paper, a novel evolutionary programming is proposed for solving the upper and lower bound optimization problems as well as the linear constrained optimization problems. There are two characteristics of the algorithm: first, only one component of the current solution is mutated in each iteration; second, it can solve the linear constrained optimization problems directly without converting it into unconstrained problems. By solving two kinds of the optimization problems, the algorithm can not only effectively find optimal or close to optimal solutions but also reduce the number of function evolutions compared with the other heuristic algorithms.     

不完全信息下的AHP优化决策方法研究

针对在紧急情况下,比如战争或灾难中利用AHP进行决策时,由于决策时间紧迫、信息掌握不完全、决策者经验限制等因素,通常会导致决策信息的不完全,提出一套完整的基于残缺判断矩阵的分析和优化的解决方案。首先,给出了残缺判断矩阵的相关定义和性质,研究了残缺判断矩阵的有效性判断的基本原理,并给出了连通图判定方法;对于无效残缺判断矩阵,通过增补最少的元素实现所有方案的互连通,从而使其成为有效残缺判断矩阵;对于有效残缺判断矩阵,提出以未知数填充残缺矩阵,构建以一致性比率最小为目标的优化决策模型;对于优化模型仍不能达到满意一致性的情形,从基本回路的不一致性分析入手,找出具有最大CR和的元素作为最不一致元素,在[1/9,9]区间上选出使得CR和最小的值作为该元素修正值,然后再构建优化模型实现最优化增补;根据以上原理,利用Matlab编程,开发了残缺判断矩阵的AHP相关决策工具软件。最后,通过算例分析验证了方法的可行性和有效性,证明了开发的软件能够满足紧急状态下决策的时效性要求,同时,通过与已有方法的对比证明了该方法更为有效。     

Two level hierarchical time minimizing transportation problem

A two level hierarchical balanced time minimizing transportation problem is considered in this paper. The whole set of source-destination links consists of two disjoint partitions namely Level-I links and Level-II links. Some quantity of a homogeneous product is first shipped from sources to destinations by Level-I decision maker using only Level-I links, and on its completion the Level-II decision maker transports the remaining quantity of the product in an optimal fashion using only Level-II links. Transportation is assumed to be done in parallel in both the levels. The aim is to find that feasible solution for Level-I decision maker corresponding to which the optimal feasible solution for Level-II decision maker is such that the sum of shipment times in Level-I and Level-II is the least. To obtain the global optimal feasible solution of this non-convex optimization problem, related balanced time minimizing transportation problems are defined. Based upon the optimal feasible solutions of these related problems, standard cost minimizing transportation problems are constructed whose optimal feasible solutions provide various pairs for shipment times for Level-I and Level-II decision makers. The best out of these pairs is finally selected. Being dependent upon solutions of a finite number of balanced time minimizing and cost minimizing transportation problems, the proposed algorithm is a polynomial bound algorithm. The developed algorithm has been implemented and tested on a variety of test problems and performance is found to be quite encouraging.     

Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization

Although recent studies have shown that evolutionary algorithms are effective tools for solving multi-objective optimization problems, their performances are often bottlenecked by the suitability of the evolutionary operators with respect to the optimization problem at hand and their corresponding parametric settings. To adapt the search dynamic of evolutionary operation in multi-objective optimization, this paper proposes an adaptive variation operator that exploits the chromosomal structure of binary representation and synergizes the function of crossover and mutation. The overall search ability is deterministically tuned online to maintain a balance between extensive exploration and local fine-tuning at different stages of the evolutionary search. Also, the coordination between the two variation operators is achieved by means of an adaptive control that ensures an efficient exchange of information between the different chromosomal sub-structures throughout the evolutionary search. Extensive comparative studies with several representative variation operators are performed on different benchmark problems and significant algorithmic performance improvements in terms of proximity, uniformity and diversity are obtained with the incorporation of the proposed adaptive variation operator into the evolutionary multi-objective optimization process.     

基于种群分类排序的约束优化遗传算法

针对约束优化问题,提出了一类将种群中的个体分类排序的思想.算法的特点在于:先将种群中的解分为可行解和不可行解两类,然后分别按照不同的标准排序.由于很多约束优化问题的最优解位于可行域的边界上或附近,所以排序时并不认为可行解一定优于不可行解.基于此分类排队思想,特别设计了只允许同等级个体进行交叉的新的交叉算子,称之为同等级交叉算子,以及基于一维搜索的变异算子.算法同时采用了保证固定比例不可行解的自适应策略.4个标准测试函数的数值仿真结果验证了算法的有效性.     

求解多层线性规划的模糊规划法

本文用模糊集理论中的隶属函数描述多层线性规划的各层目标,在第一层给定最小满意水平下,通过求解相应层次的模糊规划来确定各层的最小满意度,从而最终得到问题的一个满意解。提出的方法只需求解一系列线性规划问题,具有较好的计算复杂性和可行性,最后的算例进一步验证了方法的有效性。     

A clustering procedure for reducing the number of representative solutions in the Pareto Front of multiobjective optimization problems

In many multiobjective optimization problems, the Pareto Fronts and Sets contain a large number of solutions and this makes it difficult for the decision maker to identify the preferred ones. A possible way to alleviate this difficulty is to present to the decision maker a subset of a small number of solutions representatives of the Pareto Front characteristics.     

A genetic algorithm based augmented Lagrangian method for constrained optimization

Among the penalty based approaches for constrained optimization, augmented Lagrangian (AL) methods are better in at least three ways: (i) they have theoretical convergence properties, (ii) they distort the original objective function minimally, thereby providing a better function landscape for search, and (iii) they can result in computing optimal Lagrange multiplier for each constraint as a by-product. Instead of keeping a constant penalty parameter throughout the optimization process, these algorithms update the parameters (called multipliers) adaptively so that the corresponding penalized function dynamically changes its optimum from the unconstrained minimum point to the constrained minimum point with iterations. However, the flip side of these algorithms is that the overall algorithm requires a serial application of a number of unconstrained optimization tasks, a process that is usually time-consuming and tend to be computationally expensive. In this paper, we devise a genetic algorithm based parameter update strategy to a particular AL method. The proposed strategy updates critical parameters in an adaptive manner based on population statistics. Occasionally, a classical optimization method is used to improve the GA-obtained solution, thereby providing the resulting hybrid procedure its theoretical convergence property. The GAAL method is applied to a number of constrained test problems taken from the evolutionary algorithms (EAs) literature. The number of function evaluations required by GAAL in most problems is found to be smaller than that needed by a number of existing evolutionary based constraint handling methods. GAAL method is found to be accurate, computationally fast, and reliable over multiple runs. Besides solving the problems, the proposed GAAL method is also able to find the optimal Lagrange multiplier associated with each constraint for the test problems as an added benefit??a matter that is important for a sensitivity analysis of the obtained optimized solution, but has not yet been paid adequate attention in the past evolutionary constrained optimization studies.     

Decision making in a fuzzy environment and its application to multicriteria power engineering problems

This paper presents results of research into the use of the Bellman–Zadeh approach to decision making in a fuzzy environment for solving multicriteria optimization problems. Its application conforms to the principle of guaranteed result and provides constructive lines in obtaining harmonious solutions on the basis of analyzing associated maxmin problems. The use of the Bellman–Zadeh approach has served as a basis for solving a problem of multicriteria allocation of resources (or their shortages) and developing a corresponding adaptive interactive decision making system (AIDMS1). AIDMS1 includes procedures for considering linguistic variables to reflect conditions that are difficult to formalize as well as procedures for constructing and correcting vectors of importance factors for goals. The use of these procedures permits one to realize an adaptive approach to processing information of a decision maker to provide successive improvment in solution quality. The results of the paper are universally applicable and are already being used to solve power engineering problems. It is illustrated by considering problems of multicriteria power and energy shortage allocation and multicriteria power system operation.     

Quadratic optimization problems in robust beamforming

This paper presents a class of constrained optimization problems whereby a quadratic cost function is to be minimized with respect to a weight vector subject to an inequality quadratic constraint on the weight vector. This class of constrained optimization problems arises as a result of a motivation for designing robust antenna array processors in the field of adaptive array processing. The constrained optimization problem is first solved by using the primal-dual method. Numerical techniques are presented to reduce the computational complexity of determining the optimal Lagrange multiplier and hence the optimal weight vector. Subsequently, a set of linear constraints or at most linear plus norm constraints are developed for approximating the performance achievable with the quadratic constraint. The use of linear constraints is very attractive, since they reduce the computational burden required to determine the optimal weight vector.     

An interactive method for multiple-objective mathematical programming problems

An interactive method is developed for solving the general nonlinear multiple objective mathematical programming problems. The method asks the decision maker to provide partial information (local tradeoff ratios) about his utility (preference) function at each iteration. Using the information, the method generates an efficient solution and presents it to the decision maker. In so doing, the best compromise solution is sought in a finite number of iterations. This method differs from the existing feasible direction methods in that (i) it allows the decision maker to consider only efficient solutions throughout, (ii) the requirement of line search is optional, and (iii) it solves the problems with linear objective functions and linear utility function in one iteration. Using various problems selected from the literature, five line search variations of the method are tested and compared to one another. The nonexisting decision maker is simulated using three different recognition levels, and their impact on the method is also investigated.     

Reference point approximation method for the solution of bicriterial nonlinear optimization problems

This paper presents a reference point approximation algorithm which can be used for the interactive solution of bicriterial nonlinear optimization problems with inequality and equality constraints. The advantage of this method is that the decision maker may choose arbitrary reference points in the criteria space. Moreover, a special tunneling technique is given for the computation of global solutions of certain subproblems. Finally, the proposed method is applied to a mathematical example and a problem in mechanical engineering.     

A filled function method for constrained global optimization

In this paper, a filled function method for solving constrained global optimization problems is proposed. A filled function is proposed for escaping the current local minimizer of a constrained global optimization problem by combining the idea of filled function in unconstrained global optimization and the idea of penalty function in constrained optimization. Then a filled function method for obtaining a global minimizer or an approximate global minimizer of the constrained global optimization problem is presented. Some numerical results demonstrate the efficiency of this global optimization method for solving constrained global optimization problems.