一类新型动态多目标鲁棒进化优化方法

传统动态多目标优化问题（Dynamic multi-objective optimization problems,DMOPs）的求解方法,通常需要在新环境下,通过重新激发寻优过程,获得适应该环境的Pareto最优解.这可能导致较高的计算代价和资源成本,甚至无法在有限时间内执行该优化解.由此,提出一类寻找动态鲁棒Pareto最优解集的进化优化方法.动态鲁棒Pareto解集是指某一时刻下的Pareto较优解可以以一定稳定性阈值,逼近未来多个连续动态环境下的真实前沿,从而直接作为这些环境下的Pareto解集,以减小计算代价.为合理度量Pareto解的环境适应性,给出了时间鲁棒性和性能鲁棒性定义,并将其转化为两类鲁棒优化模型.引入基于分解的多目标进化优化方法和无惩罚约束处理方法,构建了动态多目标分解鲁棒进化优化方法.特别是基于移动平均预测模型实现了未来动态环境下适应值的多维时间序列预测.基于提出的两类新型性能评价测度,针对8个典型动态测试函数的仿真实验,结果表明该方法得到满足决策者精度要求,且具有较长平均生存时间的动态鲁棒Pareto最优解.     

DOPGA: a new fitness assignment scheme for multi-objective evolutionary algorithms

In this article, a new fitness assignment scheme to evaluate the Pareto-optimal solutions for multi-objective evolutionary algorithms is proposed. The proposed DOmination Power of an individual Genetic Algorithm (DOPGA) method can order the individuals in a form in which each individual (the so-called solution) could have a unique rank. With this new method, a multi-objective problem can be treated as if it were a single-objective problem without drastically deviating from the Pareto definition. In DOPGA, relative position of a solution is embedded into the fitness assignment procedures. We compare the performance of the algorithm with two benchmark evolutionary algorithms (Strength Pareto Evolutionary Algorithm (SPEA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2)) on 12 unconstrained bi-objective and one tri-objective test problems. DOPGA significantly outperforms SPEA on all test problems. DOPGA performs better than SPEA2 in terms of convergence metric on all test problems. Also, Pareto-optimal solutions found by DOPGA spread better than SPEA2 on eight of 13 test problems.     

An interactive evolutionary multi-objective optimization and decision making procedure

With the advent of efficient techniques for multi-objective evolutionary optimization (EMO), real-world search and optimization problems are being increasingly solved for multiple conflicting objectives. During the past decade of research and application, most emphasis has been spent on finding the complete Pareto-optimal set, although EMO researchers were always aware of the importance of procedures which would help choose one particular solution from the Pareto-optimal set for implementation. This is also one of the main issues on which the classical and EMO philosophies are divided on. In this paper, we address this long-standing issue and suggest an interactive EMO procedure which will involve a decision-maker in the evolutionary optimization process and help choose a single solution at the end. This study uses many year’s of research on EMO and would hopefully encourage both practitioners and researchers to pay more attention in viewing the multi-objective optimization as a aggregate task of optimization and decision-making.     

多目标进化算法鲁棒性实验研究*

多目标进化算法的研究主要集中于搜寻全局最优解。在现实中,环境不是一成不变的,需找到抗干扰能力强的鲁棒解。多目标鲁棒最优化问题的研究较少,主要归结于环境的不确定性和缺乏合适的测试函数。针对不同特性测试函数,通过实验检验了在不同干扰下算法的性能变化情况。实验结果表明,存在干扰的情况下,原来的测试函数不再适用,需构造鲁棒测试函数。     

On the sizing of a solar thermal electricity plant for multiple objectives using evolutionary optimization

Design, implementation and operation of solar thermal electricity plants are no more an academic task, rather they have become a necessity. In this paper, we work with power industries to formulate a multi-objective optimization model and attempt to solve the resulting problem using classical as well as evolutionary optimization techniques. On a set of four objectives having complex trade-offs, our proposed procedure first finds a set of trade-off solutions showing the entire range of optimal solutions. Thereafter, the evolutionary optimization procedure is combined with a multiple criterion decision making (MCDM) approach to focus on preferred regions of the trade-off frontier. Obtained solutions are compared with a classical generating method. Eventually, a decision-maker is involved in the process and a single preferred solution is obtained in a systematic manner. Starting with generating a wide spectrum of trade-off solutions to have a global understanding of feasible solutions, then concentrating on specific preferred regions for having a more detailed understanding of preferred solutions, and then zeroing on a single preferred solution with the help of a decision-maker demonstrates the use of multi-objective optimization and decision making methodologies in practice. As a by-product, useful properties among decision variables that are common to the obtained solutions are gathered as vital knowledge for the problem. The procedures used in this paper are ready to be used to other similar real-world problem solving tasks.     

Multi-objective genetic algorithms: problem difficulties and construction of test problems.

In this paper, we study the problem features that may cause a multi-objective genetic algorithm (GA) difficulty in converging to the true Pareto-optimal front. Identification of such features helps us develop difficult test problems for multi-objective optimization. Multi-objective test problems are constructed from single-objective optimization problems, thereby allowing known difficult features of single-objective problems (such as multi-modality, isolation, or deception) to be directly transferred to the corresponding multi-objective problem. In addition, test problems having features specific to multi-objective optimization are also constructed. More importantly, these difficult test problems will enable researchers to test their algorithms for specific aspects of multi-objective optimization.     

A simulated annealing approach to a bi-criteria sequencing problem in a two-stage supply chain

In this paper, a multi-objective simulated annealing (MOSA) solution approach is proposed to a bi-criteria sequencing problem to coordinate required set-ups between two successive stages of a supply chain in a flow shop pattern. Each production batch has two distinct attributes and a set-up occurs in each stage when the corresponding attribute of the two successive batches are different. There are two objectives including: minimizing total set-ups and minimizing the maximum number of set-ups between the two stages that are both NP-hard problems. The MOSA approach starts with an initial set of locally non-dominated solutions generated by an initializing heuristic. The set is then iteratively updated through the annealing process in search for true Pareto-optimal frontier until a stopping criterion is met. Performance of the proposed MOSA was evaluated using true Pareto-optimal solutions of small problems found via total enumeration. It was also compared against a lower bound in large problems. Comparative experiments show that the MOSA is robust in finding true Pareto-optimal solutions in small problems. It was also shown that MOSA is very well-performing in large problems and that it outperforms an existing multi-objective genetic algorithm (MOGA) in terms of quality of solutions.     

Multimodal optimization using a bi-objective evolutionary algorithm

In a multimodal optimization task, the main purpose is to find multiple optimal solutions (global and local), so that the user can have better knowledge about different optimal solutions in the search space and as and when needed, the current solution may be switched to another suitable optimum solution. To this end, evolutionary optimization algorithms (EA) stand as viable methodologies mainly due to their ability to find and capture multiple solutions within a population in a single simulation run. With the preselection method suggested in 1970, there has been a steady suggestion of new algorithms. Most of these methodologies employed a niching scheme in an existing single-objective evolutionary algorithm framework so that similar solutions in a population are deemphasized in order to focus and maintain multiple distant yet near-optimal solutions. In this paper, we use a completely different strategy in which the single-objective multimodal optimization problem is converted into a suitable bi-objective optimization problem so that all optimal solutions become members of the resulting weak Pareto-optimal set. With the modified definitions of domination and different formulations of an artificially created additional objective function, we present successful results on problems with as large as 500 optima. Most past multimodal EA studies considered problems having only a few variables. In this paper, we have solved up to 16-variable test problems having as many as 48 optimal solutions and for the first time suggested multimodal constrained test problems which are scalable in terms of number of optima, constraints, and variables. The concept of using bi-objective optimization for solving single-objective multimodal optimization problems seems novel and interesting, and more importantly opens up further avenues for research and application.     

Pareto frontier exploration in multiobjective topology optimization using adaptive weighting and point selection schemes

Topology optimization has been used in many industries and applied to a variety of design problems. In real-world engineering design problems, topology optimization problems often include a number of conflicting objective functions, such to achieve maximum stiffness and minimum mass of a design target. The existence of conflicting objective functions causes the results of the topology optimization problem to appear as a set of non-dominated solutions, called a Pareto-optimal solution set. Within such a solution set, a design engineer can easily choose the particular solution that best meets the needs of the design problem at hand. Pareto-optimal solution sets can provide useful insights that enable the structural features corresponding to a certain objective function to be isolated and explored. This paper proposes a new Pareto frontier exploration methodology for multiobjective topology optimization problems. In our methodology, a level set-based topology optimization method for a single-objective function is extended for use in multiobjective problems, using a population-based approach in which multiple points in the objective space are updated and moved to the Pareto frontier. The following two schemes are introduced so that Pareto-optimal solution sets can be efficiently obtained. First, weighting coefficients are adaptively determined considering the relative position of each point. Second, points in sparsely populated areas are selected and their neighborhoods are explored. Several numerical examples are provided to illustrate the effectiveness of the proposed method.     

基于决策者偏好区域的多目标粒子群算法研究*

多目标优化问题中,决策者往往只对目标空间的某一区域感兴趣,因此需要在这一特定的区域能够得到比较稠密的Pareto解,但传统的方法却找出全部的Pareto前沿,决策效率不高。针对该问题,给出了基于决策者偏好区域的多目标粒子群优化算法。它只求出与决策者偏好区域相关的部分Pareto最优集,从而减少了进化代数,加快收敛速度,有利于决策者进行更有效的决策。算法把解与偏好区域的距离作为影响引导者选择和剪枝策略的一个因素,运用格栅方法实现解在Pareto边界分布的均匀性。仿真结果表明该算法是有效的。     

一种基于新的模型的多目标存档遗传算法

在多目标优化中,如何在最优解集中获得一组分布均匀且质量较好的代表解是十分重要的。文中给出了种群个体的序和解的均匀性分布定义,在此基础上又给出了解的序值方差和U-度量方差,然后把对任意多个目标函数的优化问题转化成对两个目标函数的优化问题,并对转化后的优化问题提出了一种新的多目标存档遗传算法,并证明了其全局收敛性。数据实验比较表明该算法能找到问题的数量更多、分布更广、更均匀的Pareto最优解。     

Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions

Since the suggestion of a computing procedure of multiple Pareto-optimal solutions in multi-objective optimization problems in the early Nineties, researchers have been on the look out for a procedure which is computationally fast and simultaneously capable of finding a well-converged and well-distributed set of solutions. Most multi-objective evolutionary algorithms (MOEAs) developed in the past decade are either good for achieving a well-distributed solutions at the expense of a large computational effort or computationally fast at the expense of achieving a not-so-good distribution of solutions. For example, although the Strength Pareto Evolutionary Algorithm or SPEA (Zitzler and Thiele, 1999) produces a much better distribution compared to the elitist non-dominated sorting GA or NSGA-II (Deb et al., 2002a), the computational time needed to run SPEA is much greater. In this paper, we evaluate a recently-proposed steady-state MOEA (Deb et al., 2003) which was developed based on the epsilon-dominance concept introduced earlier(Laumanns et al., 2002) and using efficient parent and archive update strategies for achieving a well-distributed and well-converged set of solutions quickly. Based on an extensive comparative study with four other state-of-the-art MOEAs on a number of two, three, and four objective test problems, it is observed that the steady-state MOEA is a good compromise in terms of convergence near to the Pareto-optimal front, diversity of solutions, and computational time. Moreover, the epsilon-MOEA is a step closer towards making MOEAs pragmatic, particularly allowing a decision-maker to control the achievable accuracy in the obtained Pareto-optimal solutions.     

机组短期负荷环境／经济调度多目标混合优化

环境/经济短期负荷调度主要由调度周期内的最优机组组合和负荷环境/经济分配组成,本文将变权重多目标进化算法与混沌局部优化相结合形成混合优化算法应用到电站机组环境/经济运行多目标优化问题中,在混合多目标优化算法中采用组合结构基因,其中机组基因用于机组组合全局粗寻优,参数基因用于负荷分配局部优化,基因修正与罚函数结合解决约束问题．通过对优秀个体进行基于线性搜索的混沌局部优化,可加快收敛速度和降低计算时间．实例仿真结果说明所提出的算法能获得较好分布的Pareto优化解．     

Multi-objective community detection in complex networks

Community detection in social network analysis is usually considered as a single objective optimization problem, in which different heuristics or approximate algorithms are employed to optimize a objective function that capture the notion of community. Due to the inadequacy of those single-objective solutions, this paper first formulates a multi-objective framework for community detection and proposes a multi-objective evolutionary algorithm for finding efficient solutions under the framework. After analyzing and comparing a variety of objective functions that have been used or can potentially be used for community detection, this paper exploits the concept of correlation between objective which charcterizes the relationship between any two objective functions. Through extensive experiments on both artifical and real networks, this paper demonstrates that a combination of two negatively correlated objectives under the multi-objective framework usually leads to remarkably better performance compared with either of the orignal single objectives, including even many popular algorithms..     

Preference-based evolutionary multi-objective optimization in ship weather routing

In evolutionary multi-objective optimization (EMO) the aim is to find a set of Pareto-optimal solutions. Such approach may be applied to multiple real-life problems, including weather routing (WR) of ships. The route should be optimal in terms of passage time, fuel consumption and safety of crew and cargo while taking into account dynamically changing weather conditions. Additionally it must not violate any navigational constraints (neither static nor dynamic). Since the resulting non-dominated solutions might be numerous, some user support must be provided to enable the decision maker (DM) selecting a single “best” solution. Commonly, multi-criteria decision making methods (MCDM) are utilized to achieve this goal with DM’s preferences defined a posteriori. Another approach is to apply DM’s preferences into the very process of finding Pareto-optimal solutions, which is referred to as preference-based EMO. Here the Pareto-set is limited to those solutions, which are compliant with the pre-configured user preferences. The paper presents a new tradeoff-based EMO approach utilizing configurable weight intervals assigned to all objectives. The proposed method has been applied to ship WR problem and compared with a popular reference point method: r-dominance. Presented results prove applicability and competitiveness of the proposed method to solving multi-objective WR problem.     

Dynamic multiobjective optimization problems: test cases, approximations, and applications

After demonstrating adequately the usefulness of evolutionary multiobjective optimization (EMO) algorithms in finding multiple Pareto-optimal solutions for static multiobjective optimization problems, there is now a growing need for solving dynamic multiobjective optimization problems in a similar manner. In this paper, we focus on addressing this issue by developing a number of test problems and by suggesting a baseline algorithm. Since in a dynamic multiobjective optimization problem, the resulting Pareto-optimal set is expected to change with time (or, iteration of the optimization process), a suite of five test problems offering different patterns of such changes and different difficulties in tracking the dynamic Pareto-optimal front by a multiobjective optimization algorithm is presented. Moreover, a simple example of a dynamic multiobjective optimization problem arising from a dynamic control loop is presented. An extension to a previously proposed direction-based search method is proposed for solving such problems and tested on the proposed test problems. The test problems introduced in this paper should encourage researchers interested in multiobjective optimization and dynamic optimization problems to develop more efficient algorithms in the near future.     

A multi-objective particle swarm optimization for project selection problem

Selecting the most appropriate projects out of a given set of investment proposals is recognized as a critical issue for which the decision maker takes several aspects into consideration. Since many of these aspects may be conflicting, the problem is rendered as a multi-objective one. Consequently, we consider a multi-objective project selection problem in this study where total benefits are to be maximized while total risk and total coat must be minimized, simultaneously. Since solving an NP-hard problem becomes demanding as the number of projects grows, a multi-objective particle swarm with new selection regimes for global best and personal best for swarm members is designed to find the locally Pareto-optimal frontier and is compared with a salient multi-objective genetic algorithm, i.e. SPEAII, based on some comparison metrics with random instances.     

动态多目标优化:测试函数和算法比较

生活中存在大量的动态多目标优化问题,应用进化算法求解动态多目标优化问题受到越来越多的关注,而动态多目标测试函数对算法的评估起着重要的作用.在已有动态多目标测试函数的基础上,设计一组新的动态多目标测试函数.Pareto最优解集和Pareto前沿面的不同变化形式影响着动态多目标测试函数的难易程度,通过引入Pareto最优解集形状的变化,结合已有的Pareto最优解集移动模式,设计一组测试函数集.基于提出的测试函数集,对3个算法进行测试,仿真实验结果表明,所设计的函数给3个算法带来了挑战,并展现出算法的优劣.     

Chaos-based multi-objective immune algorithm with a fine-grained selection mechanism

In this paper, we propose a chaos-based multi-objective immune algorithm (CMIA) with a fine-grained selection mechanism based on the clonal selection principle. Taking advantage of the ergodic and stochastic properties of chaotic sequence, a novel mutation operator, named as chaos-based mutation (CM) operator, is proposed. Moreover, the information of diversity estimation is also adopted in the CM operator for nondominated solutions to adjust mutation steps adaptively, which encourages searching less-crowded regions with relative large step sizes. When comparing with polynomial mutation operator that is used in many state-of-the-art multi-objective optimization evolutionary algorithms, simulations show that it is effective to enhance the search performance. On the other hand, in order to increase the population diversity, a fine-grained selection mechanism is proposed in this paper, which seems to be remarkably effective in two-objective benchmark functions. When comparing with two state-of-the-art multi-objective evolutionary algorithms (NSGA-II and SPEA-2) and a new multi-objective immune algorithm (NNIA), simulation results of CMIA indicate the effectiveness of the fine-grained selection mechanism and the remarkable performance in finding the true Pareto-optimal front, especially on some benchmark functions with many local Pareto-optimal fronts.     

三种基于偏好的区间多目标进化算法及应用

区间参数多目标优化问题是普遍存在且非常重要的。目前直接求解该类问题的进化优化方法非常少,且已有方法的目的是找到收敛性好且分布均匀的Pareto最优解集。为得到符合决策者偏好的最满意解,本文综述3种基于偏好的区间多目标进化算法,并将其应用于特定环境下机器人路径规划问题,比较3种算法的性能。研究结果可丰富特定环境下机器人路径规划的求解方法,提高机器人路径优化效果。