基于偏好方向的区间多目标交互进化算法

区间多目标优化问题在实际应用中普遍存在且非常重要.为得到贴合决策者偏好的最满意解,采用边优化边决策的方法,提出一种交互进化算法.该算法通过请求决策者从部分非被支配解中选择一个最差解,提取决策者的偏好方向,基于该偏好方向设计反映候选解逼近性能的测度,将具有相同序值和决策者偏好的候选解排序.将所提方法应用于4个区间2目标优化问题,并与利用偏好多面体解决区间多目标优化问题的进化算法(PPIMOEA)和后验法比较,实验结果验证了所提出方法的有效性和高效性.     

数据驱动选择策略的多目标差分进化算法

针对多目标差分进化算法求解复杂多目标优化问题时,最优解选择策略中非支配排序计算复杂度高的问题,提出一种数据驱动选择策略的多目标差分进化(MODE-DDSS)算法.首先,设计多目标差分进化算法的优化解排序等级评估准则,建立基于评估准则的优化解排序等级评估库;其次,设计基于优化解双向搜索机制和无重复比较机制的数据驱动选择策略,实现优化解的高效搜索和快速排序;最后,构建数据驱动选择策略的多目标差分进化算法,降低算法在最优解选择操作中的时间复杂度,提高算法的寻优效率.实验结果表明,所提出的MODE-DDSS算法能够有效减少最优解在选择过程中的比较次数,提升多目标差分进化算法解决复杂多目标优化问题的寻优效率.     

一种求解高维优化问题的多目标遗传算法及其收敛性分析

单纯Pareto遗传算法很难解决目标数目很多的高维多目标优化问题，在多个指标之间引入偏好信息，提出的多目标遗传算法使进化群体按协调模型进行偏好排序，改变了传统的基于Pareto优于关系来比较个体的优劣。另外讨论了算法在满足一定条件下具有全局收敛性，典型算例的数学解析和实验验证了其具有较好的收敛性和收敛速度．     

基于分解和差分进化的多目标粒子群优化算法

为了提高多目标优化算法解集的分布性和收敛性,提出一种基于分解和差分进化的多目标粒子群优化算法(dMOPSO-DE).该算法通过提出方向角产生一组均匀的方向向量,确保粒子分布的均匀性;引入隐式精英保持策略和差分进化修正机制选择全局最优粒子,避免种群陷入局部最优Pareto前沿;采用粒子重置策略保证群体的多样性.与非支配排序(NSGA-II)算法、多目标粒子群优化(MOPSO)算法、分解多目标粒子群优化(dMOPSO)算法和分解多目标进化-差分进化(MOEA/D-DE)算法进行比较,实验结果表明,所提出算法在求解多目标优化问题时具有良好的收敛性和多样性.     

基于全局排序的高维多目标优化研究

目标数超过4的高维多目标优化是目前进化多目标优化领域求解难度最大的问题之一,现有的多目标进化算法求解该类问题时,存在收敛性和解集分布性上的缺陷,难以满足实际工程优化需求.提出一种基于全局排序的高维多目标进化算法GR-MODE,首先,采用一种新的全局排序策略增强选择压力,无需用户偏好及目标主次信息,且避免宽松Pareto支配在排序结果合理性与可信性上的损失;其次,采用Harmonic平均拥挤距离对个体进行全局密度估计,提高现有局部密度估计方法的精确性;最后,针对高维多目标复杂空间搜索需求,设计新的精英选择策略及适应度值评价函数.将该算法与国内外现有的5种高性能多目标进化算法在标准测试函数集DTLZ{1,2, 4,5}上进行对比实验,结果表明,该算法具有明显的性能优势,大幅提升了4~30维高维多目标优化的收敛性和分布性.     

连续空间优化问题的自适应蚁群系统算法

蚁群算法是进化计算中一种新型优化算法,其基本算法用于求解排序类型的组合优化问题本文提出一种用于连续空间优化问题求解的蚁群算法,采用了新的基于目标函数值的启发式信息素分配算法,以及搜索过程中最优解的筛选方法.根据目标函数来自适应调整蚂蚁的路径搜索行为,从而保证算法快速找到全局最优解.一个多极值点的连续优化问题求解实例证明了该方法的有效性     

自适应偏好半径划分区域的多目标进化方法

偏好多目标进化算法是一类帮助决策者找到感兴趣的Pareto最优解的算法.目前,在以参考点位置作为偏好信息载体的偏好多目标进化算法中,不合适的参考点位置往往会严重影响算法的收敛性能,偏好区域的大小难以控制,在高维问题上效果较差.针对以上问题,通过计算基于种群的自适应偏好半径,利用自适应偏好半径构造一种新的偏好关系模型,通过对偏好区域进行划分,提出基于偏好区域划分的偏好多目标进化算法.将所提算法与4种常用的以参考点为偏好信息载体的多目标进化算法g-NSGA-II、r-NSGA-II、角度偏好算法、MOEA/D-PRE进行对比实验,结果表明,所提算法具有较好的收敛性能和分布性能,决策者可以控制偏好区域大小,在高维问题上也具有较好的收敛效果.     

求解多目标优化问题的分级变异量子进化算法

分析量子进化算法和免疫算子的特点,提出一种分级变异的量子进化算法,用于求解多目标优化问题,算法主要基于两个策略:首先,利用快速非受控排序和密度距离计算种群抗原-抗体的亲和度;然后,基于亲和度排序将个体进行分级,最优分级中的个体作为算法中的最优个体,大部分实施量子旋转更新和免疫操作,而剩余分级中的个体实施免疫交叉操作以获得新的个体补充种群,求解多目标0/1背包问题的实验结果表明了该算法的有效性.     

最大化个人偏好的多目标优化进化算法

针对多目标优化过程中如何将个人偏好信息融入寻优搜索过程的问题,本文提出一种最大化个人偏好 以确定搜索方向的多目标优化进化算法．该算法首先采用权重和法将多目标问题转换为单目标问题,再利用遗传算 法进行全局搜索,在满足个人偏好约束条件下,每一代进化结束后通过解约束优化问题获得能够使种群综合适应度 具有最大方差的权重组合,从而最大化个人偏好以选择综合最优的个体进行遗传操作．按照不同个人偏好应用于传 动系统进行控制器设计,仿真结果表明该算法能够获得满足个人偏好约束条件下的全局最优解．     

进化多目标优化算法研究

进化多目标优化主要研究如何利用进化计算方法求解多目标优化问题,已经成为进化计算领域的研究热点之一.在简要总结2003年以前的主要算法后,着重对进化多目标优化的最新进展进行了详细讨论.归纳出当前多目标优化的研究趋势,一方面,粒子群优化、人工免疫系统、分布估计算法等越来越多的进化范例被引入多目标优化领域,一些新颖的受自然系统启发的多目标优化算法相继提出;另一方面,为了更有效的求解高维多目标优化问题,一些区别于传统Pareto占优的新型占优机制相继涌现;同时,对多目标优化问题本身性质的研究也在逐步深入.对公认的代表性算法进行了实验对比.最后,对进化多目标优化的进一步发展提出了自己的看法.     

Multiobjective evolutionary algorithms: a comparative case studyand the strength Pareto approach

Evolutionary algorithms (EAs) are often well-suited for optimization problems involving several, often conflicting objectives. Since 1985, various evolutionary approaches to multiobjective optimization have been developed that are capable of searching for multiple solutions concurrently in a single run. However, the few comparative studies of different methods presented up to now remain mostly qualitative and are often restricted to a few approaches. In this paper, four multiobjective EAs are compared quantitatively where an extended 0/1 knapsack problem is taken as a basis. Furthermore, we introduce a new evolutionary approach to multicriteria optimization, the strength Pareto EA (SPEA), that combines several features of previous multiobjective EAs in a unique manner. It is characterized by (a) storing nondominated solutions externally in a second, continuously updated population, (b) evaluating an individual's fitness dependent on the number of external nondominated points that dominate it, (c) preserving population diversity using the Pareto dominance relationship, and (d) incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristics. The proof-of-principle results obtained on two artificial problems as well as a larger problem, the synthesis of a digital hardware-software multiprocessor system, suggest that SPEA can be very effective in sampling from along the entire Pareto-optimal front and distributing the generated solutions over the tradeoff surface. Moreover, SPEA clearly outperforms the other four multiobjective EAs on the 0/1 knapsack problem     

An Investigation on Preference Order Ranking Scheme for Multiobjective Evolutionary Optimization

It may be generalized that all Evolutionary Algorithms (EA) draw their strength from two sources: exploration and exploitation. Surprisingly, within the context of multiobjective (MO) optimization, the impact of fitness assignment on the exploration-exploitation balance has drawn little attention. The vast majority of multiobjective evolutionary algorithms (MOEAs) presented to date resort to Pareto dominance classification as a fitness assignment methodology. However, the proportion of Pareto optimal elements in a set P grows with the dimensionality of P. Therefore, when the number of objectives of a multiobjective problem (MOP) is large, Pareto dominance-based ranking procedures become ineffective in sorting out the quality of solutions. This paper investigates the potential of using preference order-based approach as an optimality criterion in the ranking stage of MOEAs. A ranking procedure that exploits the definition of preference ordering (PO) is proposed, along with two strategies that make different use of the conditions of efficiency provided, and it is compared with a more traditional Pareto dominance-based ranking scheme within the framework of NSGA-II. A series of extensive experiments is performed on seven widely applied test functions, namely, DTLZ1, DTLZ2, DTLZ3, DTLZ4, DTLZ5, DTLZ6, and DTLZ7, for up to eight objectives. The results are analyzed through a suite of five performance metrics and indicate that the ranking procedure based on PO enables NSGA-II to achieve better scalability properties compared with the standard ranking scheme and suggest that the proposed methodology could be successfully extended to other MOEAs     

基于精英进化导向的多目标PID参数优化

在多目标优化问题中,决策者必须对Pareto前沿的众多非劣解做出选择.本文将决策偏好融入Pareto优化过程,提出一种基于精英导向机制的多目标遗传算法,根据决策偏好选择Pareto最优解为精英,利用无损有限精度法和归一增量距离保持种群多样性,通过多种群进化机制将决策偏好的影响传播到整个种群.该方法成功应用于自动导引车(AGV)伺服系统的PID参数优化,可根据决策偏好快速有效地定向搜索Pareto最优解,保证伺服控制达到路径跟踪要求的速度响应性能.     

A comparative study of different approaches using an outranking relation in a multi-objective evolutionary algorithm

This paper presents a comparative analysis of three versions of an evolutionary algorithm in which the decision maker's preferences are incorporated using an outranking relation and preference parameters associated with the ELECTRE TRI method. The aim is using the preference information supplied by the decision maker to guide the search process to the regions where solutions more in accordance with his/her preferences are located, thus narrowing the scope of the search and reducing the computational effort. An example dealing with a pertinent problem in electrical distribution network is used to compare the different versions of the algorithm and illustrate how meaningful information can be elicited from a decision maker and used in the operational framework of an evolutionary algorithm to provide decision support in real-world problems.     

一种解决多目标优化问题改进的进化规划算法

目前,大多数多目标进化算法采用非优超排序的方法逼近Pareto前沿,此方法存在的一个致命弱点是需要花费大量的时间检验非劣解,效率很低。论文提出了一种新的多目标进化规划算法,将初始群体划分为可替换部分与不可替换部分,并用外部文件存储进化过程中得到的非劣解,大大减少了检验非劣解所需的工作,加快了算法的收敛速度。仿真试验表明,与传统的基于非优超排序的多目标进化规划算法相比,该算法在效率上有很大的改善,并能更好地逼近Pareto前沿。     

Multiobjective optimization and multiple constraint handling withevolutionary algorithms. I. A unified formulation

In optimization, multiple objectives and constraints cannot be handled independently of the underlying optimizer. Requirements such as continuity and differentiability of the cost surface add yet another conflicting element to the decision process. While “better” solutions should be rated higher than “worse” ones, the resulting cost landscape must also comply with such requirements. Evolutionary algorithms (EAs), which have found application in many areas not amenable to optimization by other methods, possess many characteristics desirable in a multiobjective optimizer, most notably the concerted handling of multiple candidate solutions. However, EAs are essentially unconstrained search techniques which require the assignment of a scalar measure of quality, or fitness, to such candidate solutions. After reviewing current revolutionary approaches to multiobjective and constrained optimization, the paper proposes that fitness assignment be interpreted as, or at least related to, a multicriterion decision process. A suitable decision making framework based on goals and priorities is subsequently formulated in terms of a relational operator, characterized, and shown to encompass a number of simpler decision strategies. Finally, the ranking of an arbitrary number of candidates is considered. The effect of preference changes on the cost surface seen by an EA is illustrated graphically for a simple problem. The paper concludes with the formulation of a multiobjective genetic algorithm based on the proposed decision strategy. Niche formation techniques are used to promote diversity among preferable candidates, and progressive articulation of preferences is shown to be possible as long as the genetic algorithm can recover from abrupt changes in the cost landscape     

进化高维多目标优化研究进展

高维多目标优化问题是目标个数多于3的多目标优化问题.尽管进化优化方法在多目标优化问题求解中显示了卓越的性能,但是,对于高维多目标优化问题,已有方法存在目标维数难以扩展、Pareto占优关系无法区分进化个体,以及多样性维护策略失效等困难.因此,高维多目标优化问题的高效求解引起进化优化界的高度关注.本文将分别从新型占优关系、多样性维护策略、目标缩减、目标聚合、基于性能指标的选择、融入偏好、集合进化、变化算子、可视化技术,以及应用等10个方面分类总结近年来进化高维多目标优化的研究成果,通过分析已有研究存在的问题,指出今后可能的研究方向.     

A new graphical visualization of n-dimensional Pareto front for decision-making in multiobjective optimization

New challenges in engineering design lead to multiobjective (multicriteria) problems. In this context, the Pareto front supplies a set of solutions where the designer (decision-maker) has to look for the best choice according to his preferences. Visualization techniques often play a key role in helping decision-makers, but they have important restrictions for more than two-dimensional Pareto fronts. In this work, a new graphical representation, called Level Diagrams, for n-dimensional Pareto front analysis is proposed. Level Diagrams consists of representing each objective and design parameter on separate diagrams. This new technique is based on two key points: classification of Pareto front points according to their proximity to ideal points measured with a specific norm of normalized objectives (several norms can be used); and synchronization of objective and parameter diagrams. Some of the new possibilities for analyzing Pareto fronts are shown. Additionally, in order to introduce designer preferences, Level Diagrams can be coloured, so establishing a visual representation of preferences that can help the decision-maker. Finally, an example of a robust control design is presented - a benchmark proposed at the American Control Conference. This design is set as a six-dimensional multiobjective problem.     

A method for multiple pseudo-criteria decision problems

Most complex decision problems involve conflicting multicriteria to be reconciled. It is not uncommon that the numerical values of alternatives of some criteria are subject to imprecision, uncertainty, and indetermination. The concept of pseudo-criterion and its two thresholds allow them to be taken into account. So far, outranking relation methods, which are called ELECTRE I–IV and others, in which an outranking relation between alternatives is constructed from pseudo-criteria have been developed. Among others, ELECTRE III is the most familiar and has been widely used. The purpose of this paper is to propose a new procedure for treating the pseudo-criterion based on the ternary AHP. This procedure differs from ELECTRE III and requires only the incomplete information on the weights but not precise weights. Strict preference, weak preference, and indifference relations associated with a pseudo-criterion are formulated by a ternary comparison. In general, the procedures for dealing with the pseudo-criterion necessarily involve a certain amount of arbitrariness. Therefore, it is preferable to derive the rankings of alternatives from several procedures for the pseudo-criterion in order to promote complementary viewpoints. Comparing our procedure with ELECTRE III, the strengths and weaknesses of the proposed procedure are discussed.Scope and purposeMost decision problems involve multiple and conflicting objectives, goals, or attributes. In the past three decades, many approaches have been developed. These include decision analysis based on multiattribute utility theory and interactive approaches based on the progressive articulation of preferences. They are built on sound theoretical foundations but rely on strict assumptions about the underlying preference structure. It is not uncommon that the numerical values of alternatives of some criteria are imprecise and ambiguous in complex decision problems. In such cases, the above approaches may not be appropriate. To cope with them, the concept of pseudo-criterion was introduced. So far, the outranking relation methods based on the pseudo-criterion which do not require the assumption of transitivity nor the complete comparability in the underlying preference structure have been developed. In this paper, we propose a new procedure for treating the pseudo-criterion based on the ternary AHP that differs from the outranking relation methods. In general, the procedures for dealing with the pseudo-criterion necessarily involve a certain amount of arbitrariness. Therefore, it is preferable to derive the rankings of alternatives from several procedures based on the pseudo-criterion in order to promote complementary viewpoints.     

Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.