基于决策空间变换最近邻方法的Pareto支配性预测

为提高在决策空间运用最近邻方法预测多目标优化Pareto支配性的精度，提出一种基于决策空间变换的最近邻预测方法.在分析目标函数与决策分量相关性的基础上，提出属性变化趋势模型的构造方法，建立低计算成本的属性趋势代理模型.通过属性趋势模型引入决策空间到目标空间的映射知识，对多目标问题的决策空间进行变换，使决策空间的最近邻更有效反映目标空间的最近邻.选取具有不同相关系数特征的典型多目标优化问题，进行Pareto支配性预测的可对比实验，结果表明在新空间中运用最近邻方法可显著提高分类准确性.     

Estimation of the Pareto front in stochastic simulation through stochastic Kriging

Multi-objective optimization of simulated stochastic systems aims at estimating a representative set of Pareto optimal solutions and a common approach is to rely on metamodels to alleviate computational costs of the optimization process. In this article, both the objective and constraint functions are assumed to be smooth, highly non-linear and computationally expensive and are emulated by stochastic Kriging models. Then a novel global optimization algorithm, combing the expected hypervolume improvement of approximated Pareto front and the probability of feasibility of new points, is proposed to identify the Pareto front (set) with a minimal number of expensive simulations. The algorithm is suitable for the situations of having disconnected feasible regions and of having no feasible solution in initial design. Then, we also quantify the variability of estimated Pareto front caused by the intrinsic uncertainty of stochastic simulation using nonparametric bootstrapping method to better support decision making. One test function and an (s, S) inventory system experiment illustrate the potential and efficiency of the proposed sequential optimization algorithm for constrained multi-objective optimization problems in stochastic simulation, which is especially useful in Operations Research and Management Science.     

Approximating the Set of Pareto-Optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution Algorithm

Most existing multiobjective evolutionary algorithms aim at approximating the Pareto front (PF), which is the distribution of the Pareto-optimal solutions in the objective space. In many real-life applications, however, a good approximation to the Pareto set (PS), which is the distribution of the Pareto-optimal solutions in the decision space, is also required by a decision maker. This paper considers a class of multiobjective optimization problems (MOPs), in which the dimensionalities of the PS and the PF manifolds are different so that a good approximation to the PF might not approximate the PS very well. It proposes a probabilistic model-based multiobjective evolutionary algorithm, called MMEA, for approximating the PS and the PF simultaneously for an MOP in this class. In the modeling phase of MMEA, the population is clustered into a number of subpopulations based on their distribution in the objective space, the principal component analysis technique is used to estimate the dimensionality of the PS manifold in each subpopulation, and then a probabilistic model is built for modeling the distribution of the Pareto-optimal solutions in the decision space. Such a modeling procedure could promote the population diversity in both the decision and objective spaces. MMEA is compared with three other methods, KP1, Omni-Optimizer and RM-MEDA, on a set of test instances, five of which are proposed in this paper. The experimental results clearly suggest that, overall, MMEA performs significantly better than the three compared algorithms in approximating both the PS and the PF.     

A multiobjective hybrid ant colony optimization approach applied to the assignment and scheduling problem

The assignment and scheduling problem is inherently multiobjective. It generally involves multiple conflicting objectives and large and highly complex search spaces. The problem allows the determination of an efficient allocation of a set of limited and shared resources to perform tasks, and an efficient arrangement scheme of a set of tasks over time, while fulfilling spatiotemporal constraints. The main objective is to minimize the project makespan as well as the total cost. Finding a good approximation set is the result of trade‐offs between diversity of solutions and convergence toward the Pareto‐optimal front. It is difficult to achieve such a balance with NP‐hard problems. In this respect, and in order to efficiently explore the search space, a hybrid bidirectional ant‐based approach is proposed in this paper, which is an improvement of a bi‐colony ant‐based approach. Its main characteristic is that it combines a solution construction developed for a more complicated problem with a Pareto‐guided local search engine.     

Rank-density-based multiobjective genetic algorithm and benchmark test function study

Concerns the use of evolutionary algorithms (EA) in solving multiobjective optimization problems (MOP). We propose the use of a rank-density-based genetic algorithm (RDGA) that synergistically integrates selected features from existing algorithms in a unique way. A new ranking method, automatic accumulated ranking strategy, and a "forbidden region" concept are introduced, completed by a revised adaptive cell density evaluation scheme and a rank-density-based fitness assignment technique. In addition, four types of MOP features, such as discontinuous and concave Pareto front, local optimality, high-dimensional decision space and high-dimensional objective space are exploited and the corresponding MOP test functions are designed. By examining the selected performance indicators, RDGA is found to be statistically competitive with four state-of-the-art algorithms in terms of keeping the diversity of the individuals along the tradeoff surface, tending to extend the Pareto front to new areas and finding a well-approximated Pareto optimal front.     

基于平衡搜索策略的多目标粒子群优化算法*

鉴于平衡全局和局部搜索在多目标粒子群优化算法获取完整均匀Pareto最优前沿方面的重要性,设计平衡全局和局部搜索策略,进而提出改进的多目标粒子群优化算法(bsMOPSO).文中策略在局部搜索方面设计归档集自挖掘子策略,通过对归档集中均匀分布的部分粒子进行柯西扰动,使归档集涵盖整个前沿面的局部搜索.在全局搜索方面设计边界最优粒子引导搜索子策略,以边界最优粒子替换部分粒子的全局最优解,引导粒子向各维目标的边界区域搜索.选取4种对比算法在ZDT和DTLZ系列的部分测试函数上进行实验,结果表明bsMOPSO具有更快的Pareto最优前沿收敛效率和更好的分布性.     

基于空间网格划分的多目标进化算法

为了有效求解多目标优化问题,找到分布宽广、均匀的Pareto解集,提出了一个基于空间网格划分的进化算法。将目标空间网格化,利用网格的位置,删除大量被支配个体。在杂交算子中利用了单个目标最优的个体信息,以增加非劣解的宽广性。利用一种新设计的基于最大距离排序的方法删除非劣解集中多余个体。数值实验表明提出的算法是可行有效的。     

Searching for knee regions of the Pareto front using mobile reference points

Evolutionary Algorithms (EAs) have been recognized to be well suited to approximate the Pareto front of Multi-objective Optimization Problems (MOPs). In reality, the Decision Maker (DM) is not interested in discovering the whole Pareto front rather than finding only the portion(s) of the front that matches at most his/her preferences. Recently, several studies have addressed the decision-making task to assist the DM in choosing the final alternative. Knee regions are potential parts of the Pareto front presenting the maximal trade-offs between objectives. Solutions residing in knee regions are characterized by the fact that a small improvement in either objective will cause a large deterioration in at least another one which makes moving in either direction not attractive. Thus, in the absence of explicit DM’s preferences, we suppose that knee regions represent the DM’s preferences themselves. Recently, few works were proposed to find knee regions. This paper represents a further study in this direction. Hence, we propose a new evolutionary method, denoted TKR-NSGA-II, to discover knee regions of the Pareto front. In this method, the population is guided gradually by means of a set of mobile reference points. Since the reference points are updated based on trade-off information, the population converges towards knee region centers which allows the construction of a neighborhood of solutions in each knee. The performance assessment of the proposed algorithm is done on two- and three-objective knee-based test problems. The obtained results show the ability of the algorithm to: (1) find the Pareto optimal knee regions, (2) control the extent (We mean by extent the breadth/spread of the obtained knee region.) of the obtained regions independently of the geometry of the front and (3) provide competitive and better results when compared to other recently proposed methods. Moreover, we propose an interactive version of TKR-NSGA-II which is useful when the DM has no a priori information about the number of existing knees in the Pareto optimal front.     

Decision Boundary Visualization for Counterfactual Reasoning

Machine learning algorithms are widely applied to create powerful prediction models. With increasingly complex models, humans' ability to understand the decision function (that maps from a high-dimensional input space) is quickly exceeded. To explain a model's decisions, black-box methods have been proposed that provide either non-linear maps of the global topology of the decision boundary, or samples that allow approximating it locally. The former loses information about distances in input space, while the latter only provides statements about given samples, but lacks a focus on the underlying model for precise ‘What-If'-reasoning. In this paper, we integrate both approaches and propose an interactive exploration method using local linear maps of the decision space. We create the maps on high-dimensional hyperplanes—2D-slices of the high-dimensional parameter space—based on statistical and personal feature mutability and guided by feature importance. We complement the proposed workflow with established model inspection techniques to provide orientation and guidance. We demonstrate our approach on real-world datasets and illustrate that it allows identification of instance-based decision boundary structures and can answer multi-dimensional ‘What-If'-questions, thereby identifying counterfactual scenarios visually.     

混合多目标粒子群优化算法在热精轧负荷分配优化中的应用

通过对热精轧负荷分配过程的分析,选取负荷均衡、板形良好和轧制功率最低为目标,建立了热精轧负荷分配多目标优化模型.为了提高多目标优化算法解集的分布性和收敛性,提出了一种混合多目标粒子群优化算法(HMOPSO),该算法根据Pareto支配关系得到Pareto前沿进而保证种群收敛;采用分解策略维护外部存档,该策略首先根据Pareto前沿求出上界点对目标空间进行归一化处理,然后对种群进行分区处理进而保证种群的分布性能.仿真结果表明,HMOPSO的收敛性和分布性都好于MOPSO和d MOPSO;采用模糊多属性决策的方法从Pareto最优解集中选择一个Pareto最优解,通过与经验负荷分配方法相比,表明该Pareto最优解可以使轧制方案更加合理.     

A radial space division based evolutionary algorithm for many-objective optimization

In evolutionary many-objective optimization, diversity maintenance plays an important role in pushing the population towards the Pareto optimal front. Existing many-objective evolutionary algorithms mainly focus on convergence enhancement, but pay less attention to diversity enhancement, which may fail to obtain uniformly distributed solutions or fall into local optima. This paper proposes a radial space division based evolutionary algorithm for many-objective optimization, where the solutions in high-dimensional objective space are projected into the grid divided 2-dimensional radial space for diversity maintenance and convergence enhancement. Specifically, the diversity of the population is emphasized by selecting solutions from different grids, where an adaptive penalty based approach is proposed to select a better converged solution from the grid with multiple solutions for convergence enhancement. The proposed algorithm is compared with five state-of-the-art many-objective evolutionary algorithms on a variety of benchmark test problems. Experimental results demonstrate the competitiveness of the proposed algorithm in terms of both convergence enhancement and diversity maintenance.     

Integrating Conjugate Gradients Into Evolutionary Algorithms for Large-Scale Continuous Multi-Objective Optimization

Large-scale multi-objective optimization problems (LSMOPs) pose challenges to existing optimizers since a set of well-converged and diverse solutions should be found in huge search spaces. While evolutionary algorithms are good at solving small-scale multi-objective optimization problems, they are criticized for low efficiency in converging to the optimums of LSMOPs. By contrast, mathematical programming methods offer fast convergence speed on large-scale single-objective optimization problems, but they have difficulties in finding diverse solutions for LSMOPs. Currently, how to integrate evolutionary algorithms with mathematical programming methods to solve LSMOPs remains unexplored. In this paper, a hybrid algorithm is tailored for LSMOPs by coupling differential evolution and a conjugate gradient method. On the one hand, conjugate gradients and differential evolution are used to update different decision variables of a set of solutions, where the former drives the solutions to quickly converge towards the Pareto front and the latter promotes the diversity of the solutions to cover the whole Pareto front. On the other hand, objective decomposition strategy of evolutionary multi-objective optimization is used to differentiate the conjugate gradients of solutions, and the line search strategy of mathematical programming is used to ensure the higher quality of each offspring than its parent. In comparison with state-of-the-art evolutionary algorithms, mathematical programming methods, and hybrid algorithms, the proposed algorithm exhibits better convergence and diversity performance on a variety of benchmark and real-world LSMOPs.      

Multi-objective genetic programming approach for robust modeling of complex manufacturing processes having probabilistic uncertainty in experimental data

In this paper, a multi-objective uniform-diversity genetic programming (MUGP) algorithm deployed for robust Pareto modeling and prediction of complex nonlinear processes using some input-output data table. The uncertainties included in measured data are considered to obtain more robust models. The considered benchmarks are an explosive cutting and forming processes, in which the nonlinear behavior between the input and output of processes are detected using MUGP. For both case studies, a multi-objective modeling and prediction procedure firstly performed using deterministic data. Secondly, the same identification procedure carried out using probabilistic uncertainty in the experimental input-output data. The objective functions considered are namely, training error, prediction error and number of tree nodes (complexity of models) in the deterministic approach. Accordingly, the mean and standard deviation of training error and prediction error are considered in robust Pareto modeling and prediction of such processes. In this way, Pareto front of such modeling and prediction is first obtained for both explosive cutting and forming processes with deterministic data. Such Pareto front is then obtained using experimental input-output-data having probabilistic uncertainty in input parameters through a Monte Carlo simulation (MCS) approach. In addition, it has been shown that for both cases, the trade-off models obtained from deterministic data have significant biases when tested on data with probabilistic uncertainty. Finally, the obtained results of such multi-objective robust model identification show promising results in terms of compensating uncertainty in the experimental input-output-data.     

多目标优化Knee前沿搜索方法研究进展

多目标优化算法是近年来进化计算研究领域的一个热点,大多数的多目标优化算法试图找到问题的完整的Pareto前沿.然而,随着待优化问题目标个数的增加,算法需要更大的种群规模才能合理地描绘出完整的Pareto前沿.显然这样不仅增加了算法的运行时间,更增加了(决策者)最终解的选择难度.因此,聚焦于搜索Pareto前沿上的特定区域显得尤为重要,近年来也得到了越来越多学者的关注. Knee点指的是Pareto前沿上具有最大边际效用的点,在这个点附近,一个目标值的微小提升将带来至少一个其他目标值的巨大衰退,因此该点通常被认为是在没有特殊偏好的情况下对决策者更具吸引力的点.本文旨在对多目标优化中Knee前沿搜索相关的方法进行总结,包括Knee的检测方法、保留策略、测试问题等,并对多目标优化的Knee前沿搜索未来研究工作进行展望.     

Multi-objective evolutionary approach to prevent premature convergence in Monte Carlo localization

In this paper, we propose a global localization algorithm for mobile robots based on Monte Carlo localization (MCL), which employs multi-objective particle swarm optimization (MOPSO) incorporating a novel archiving strategy, to deal with the premature convergence problem in global localization in highly symmetrical environments. Under three proposed rules, premature convergence occurring during the localization can be easily detected so that the proposed MOPSO is introduced to obtain a uniformly distributed Pareto front based on two objective functions respectively representing weights and distribution of particles in MCL. On the basis of the derived Pareto front, MCL is able to resample particles with balanced weights as well as diverse distribution of the population. As a consequence, the proposed approach provides better diversity for particles to explore the environment, while simultaneously maintaining good convergence to achieve a successful global localization. Simulations have confirmed that the proposed approach can significantly improve global localization performance in terms of success rate and computational time in highly symmetrical environments.     

Pareto最大最小蚂蚁算法及其在热轧批量计划优化中的应用

针对双目标旅行商问题提出了基于Pareto概念的最大最小蚂蚁算法(P--MMAS). 通过重新设计状态转移策略、信息素更新策略及局部搜索策略, 同时引入基于自适应网格的多样性保持策略与信息素平滑机制, 使算法能够快速搜索到在目标空间上均匀分布的近似Pareto前端. 通过在6个标准测试函数上的实验及在热轧批量计划优化中的应用, 表明P--MMAS具有良好的优化性能及实用性.     

A Novel Multiobjective Fireworks Algorithm and Its Applications to Imbalanced Distance Minimization Problems

Recently, multimodal multiobjective optimization problems (MMOPs) have received increasing attention. Their goal is to find a Pareto front and as many equivalent Pareto optimal solutions as possible. Although some evolutionary algorithms for them have been proposed, they mainly focus on the convergence rate in the decision space while ignoring solutions diversity. In this paper, we propose a new multiobjective fireworks algorithm for them, which is able to balance exploitation and exploration in the decision space. We first extend a latest single-objective fireworks algorithm to handle MMOPs. Then we make improvements by incorporating an adaptive strategy and special archive guidance into it, where special archives are established for each firework, and two strategies (i.e., explosion and random strategies) are adaptively selected to update the positions of sparks generated by fireworks with the guidance of special archives. Finally, we compare the proposed algorithm with eight state-of-the-art multimodal multiobjective algorithms on all 22 MMOPs from CEC2019 and several imbalanced distance minimization problems. Experimental results show that the proposed algorithm is superior to compared algorithms in solving them. Also, its runtime is less than its peers’.      

A multiobjective approach for maximizing the reach or GRP of different brands in TV advertising

This paper focuses on a multiobjective optimization problem in TV advertising from an advertising agency's perspective, which involves deciding on which commercial breaks to air the ads of various brands to jointly maximize reach or gross rating point (GRP) for the different brands subject to budget constraints, brand competition constraints, and other scheduling constraints. We present a multiobjective integer programming formulation of this problem and develop and implement algorithms for generating provably Pareto‐optimal solutions. We also develop reduction and visualization procedures to aid a decision maker in choosing suitable subsets of the Pareto‐optimal solutions obtained. Numerical experiments on five TV advertising problems involving 20–40 objective functions and thousands of decision variables and constraints demonstrate the effectiveness of the proposed formulation and solution methods in generating Pareto‐optimal objective vectors that reflect brand priorities and that are well distributed along the Pareto front.     

Adaptive generalisation

Adaptive generalisation is the ability to use prior knowledge in the performance of novel tasks. Thus, if we are to model intelligent behaviour with neural nets, they must be able to generalise across task domains. Our objective is to elucidate the aetiology of transfer of information between connectionist nets. First, a method is described that provides a standardised score for the quantification of how much task structure a net has extracted, and to what degree knowledge has been transferred between tasks. This method is then applied in three simulation studies to examine Input-to-Hidden (IH) and Hidden-to-Output (HO) decision hyperplanes as determinants of transfer effects. In the first study, positive transfer is demonstrated between functions that require the vertices of their spaces to be divided similarly, and negative transfer between functions that require decision regions of different shapes. In the other two studies, input and output similarity are varied independently in a series of paired associate learning tasks. Further explanation of transfer effects is provided through the use of a new technique that permits better visualisation of the entire computational space by showing both the relative position of inputs in Hidden Unit space, and the HO decision regions implemented by the set of weights.This research was supported by an award from the Economic and Social Research Council, Grant No R000233441. An earlier version of this paper appears in the Proceedings of the Second Irish Networks Conference, Belfast 1992.     

基于在线感知Pareto前沿划分目标空间的多目标进化优化

多目标进化优化是求解多目标优化问题的可行方法.但是, 由于没有准确感知并充分利用问题的Pareto前沿, 已有方法难以高效求解复杂的多目标优化问题.本文提出一种基于在线感知Pareto前沿划分目标空间的多目标进化优化方法, 以利用感知的结果, 采用有针对性的进化优化方法求解多目标优化问题.首先, 根据个体之间的拥挤距离与给定阈值的关系感知优化问题的Pareto前沿上的间断点, 并基于此将目标空间划分为若干子空间; 然后, 在每一子空间中采用MOEA/D (Multi-objective evolutionary algorithm based on decomposition)得到一个外部保存集; 最后, 基于所有外部保存集生成问题的Pareto解集.将提出的方法应用于15个基准数值函数优化问题, 并与NSGA-Ⅱ、RPEA、MOEA/D、MOEA/DPBI、MOEA/D-STM和MOEA/D-ACD等比较.结果表明, 提出的方法能够产生收敛和分布性更优的Pareto解集, 是一种非常有竞争力的方法.