一种基于最小生成树的多目标进化算法

怎样保证朝Pareto最优解的方向搜索和如何获得均匀分布且范围广泛的非支配解是多目标进化算法(MOEA)设计时的两个关键问题,它们很大程度上取决于适应度赋值和外部种群维护这两个重要部分.提出了一种基于最小生成树的多目标进化算法(MST_MOEA).在考虑了个体间支配关系的基础上,利用个体与非支配集的距离和不同等级个体的树聚集密度来对适应度赋值;在外部种群的非支配解个数超过规定的种群规模时,用树的度数和树聚集密度对其进行修剪.将其应用于不同维数下9个测试函数,并与NSGA-II,SPEA2进行对比,结果证实了算法良好的收敛性和分布性.     

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。     

基于邻域竞赛的多目标优化算法

传统多目标优化算法（Multi-objective evolution algorithms,MOEAs）的基本框架大致分为两部分:首先是收敛性保持,采用Pareto支配方法将种群分成若干非支配层;其次是分布性保持,在临界层中,采用分布性保持机制维持种群的分布性.然而在处理高维优化问题（Many-objective optimization problems,MOPs）（目标维数大于3）时,随着目标维数的增加,种群的收敛性和分布性的冲突加剧,Pareto支配关系比较个体优劣的能力也迅速下降,此时传统的MOEA已不再适用于高维优化问题.鉴于此,本文提出了一种基于邻域竞赛的多目标优化算法（Evolutionary algorithm based on neighborhood competition for multi-objective optimization,NCEA）.NCEA首先将个体的各个目标之和作为个体的收敛性估计;然后,计算当前个体向量与收敛性最好的个体向量之间的夹角,并将其作为当前个体的邻域估计;最后,通过邻域竞赛方法将问题划分为若干个相互关联的子问题并逐步优化.为了验证NCEA的有效性,本文选取5个优秀的算法与NCEA进行对比实验.通过对比实验验证,NCEA具有较强的竞争力,能同时保持良好的收敛性和分布性.     

基于控制流图支配树的测试数据灰度编码生成

为进一步提高数据测试算法性能,提出一种基于控制流图支配树的测试数据灰度编码进化生成算法。首先,利用三角分类程序示例构建数据测试的数据流控制流图,并利用其支配树关系构建测试数据的数据流分析,建立程序变量间的支配关系集;其次,结合遗传算法并利用支配关系及分支距离构建测试数据生成的适应值函数,同时在应用遗传算法时,采用灰度编码方式取代二进制编码,简化编码更新过程;最后,通过在测试程序样例中的实验对比显示,本文所提方法在测试性能上得到明显提升。     

一种基于投影和树的闭合频繁模式算法

提出一种基于投影和树的闭合频繁模式挖掘的算法.此算法利用一种数据结构:投影和树,把事务投影到这棵前缀树上,它除了可以从空间上紧凑地存放频繁模式外,还建立了层的概念,挖掘时充分利用已有的计算结果,不重复计算.另外挖掘时,算法只对投影和树进行一次遍历,不需要进行耗时的I/O操作,也不需要递归地建立条件FP树而消耗大量的CPU计算资源.实验结果表明在稠密集上,其效率较高.     

基于空间距离的多目标进化算法

为提高多目标进化算法的收敛性,提出一种基于空间距离的多目标进化算法.定义一种密度估计指标--树聚集距离,在考虑非支配前沿的同时,利用个体的空间距离及树聚集距离进行个体选择操作.另外,在外部种群的非支配解个数超过规定的种群规模时,用基于个体邻近距离的维护方法对其进行维护.通过6个测试问题和5个方面的测试标准,与NSGA-Ⅱ和SPEA2进行比较,该算法在拥有更好收敛度的同时,保持良好的均匀性和分布广度.     

基于角度邻域的多目标差分进化算法

针对如何实现差分进化算法求解多目标优化问题,提出了一种基于角度邻域的多目标差分进化算法,通过在选择操作中引入弱支配概念,实现了对多目标优化问题的求解.该算法通过计算目标空间中个体与权重向量的夹角来确定每个个体的邻域,并在此基础上引入了基于角度邻域的变异策略,使个体的变异在邻域内进行,保证进化方向.此外,该算法创建了一个外部存档用来保存进化过程中的非支配解,并定期对外部存档进行维护,大大改善了解集的分布性.大量的数值仿真实验结果表明通过角度确定邻域的方法比通过欧氏距离确定邻域的方法更加有效,算法所得解集的收敛性和分布性也均明显优于基于分解的差分多目标进化算法(multiobjective evolutionary algorithm based on decomposition and differential evolution,MOEA/D–DE)和非支配排序算法Ⅱ(nondominated sorting genetic algorithm II,NSGA).     

Rough集中U/P的快速算法

针对目前计算Rough集中U/P算法需要重复扫描决策系统、不断地进行属性值比较和排序的缺点,提出了一种基于树型结构的不可区分关系树,通过不可区分关系树实现了计算U/P的快速算法.该算法只需扫描一次决策系统,并且也避免了不断地进行属性值比较和排序.经实验验证该算法较目前基于排序的U/P算法更快,而且算法实现更简洁.     

基于R树的无线传感器网络节点管理技术

集成了计算、通信和传感器这三项技术的无线传感器网络是一种全新的信息获取和处理技术.在简单介绍传感器网络和R树相关知识的基础上,针对传感器网络的特点提出一种基于R树的传感器节点管理方法.该方法可以把传感器网络中节点的空间信息有效地管理起来,进而扩充传感器网络的功能.最后,基于这种管理方法分别给出空间区域查询和空间权限管理的解决方法.     

基于本体语义树的主题空间向量模型

在传统检索模型的基础上,结合本体的概念,提出一种基于本体语义树的主题空间向量模型,该模型能够用语义概念树描述一个主题,与传统基于关键词描述主题的方法不同,它能够描述概念之间的简单语义关系.在此基础上,给出HTML页面内容与主题相关度的计算方法.在分析URL的相关度时,不仅分析链接锚文本与主题相关度,还结合了改进的Pag...     

Achieving balance between proximity and diversity in multi-objective evolutionary algorithm

Currently, an alternative framework using the hypervolume indicator to guide the search for elite solutions of a multi-objective problem is studied in the evolutionary multi-objective optimization community very actively, comparing to the traditional Pareto dominance based approach. In this paper, we present a dynamic neighborhood multi-objective evolutionary algorithm based on hypervolume indicator (DNMOEA/HI), which benefits from both Pareto dominance and hypervolume indicator based frameworks. DNMOEA/HI is featured by the employment of hypervolume indicator as a truncation operator to prune the exceeded population, while a well-designed density estimator (i.e., tree neighborhood density) is combined with the Pareto strength value to perform fitness assignment. Moreover, a novel algorithm is proposed to directly evaluate the hypervolume contribution of a single individual. The performance of DNMOEA/HI is verified on a comprehensive benchmark suite, in comparison with six other multi-objective evolutionary algorithms. Experimental results demonstrate the efficiency of our proposed algorithm. Solutions obtained by DNMOEA/HI well approach the Pareto optimal front and are evenly distributed over the front, simultaneously.     

An augmented multi-objective particle swarm optimizer for building cluster operation decisions

It is envisioned that other than the grid-building communication, the smart buildings could potentially treat connected neighborhood buildings as a local buffer thus forming a local area energy network through the smart grid. As the hardware technology is in place, what is needed is an intelligent algorithm that coordinates a cluster of buildings to obtain Pareto decisions on short time scale operations. Research has proposed a memetic algorithm (MA) based framework for building cluster operation decisions and it demonstrated the framework is capable of deriving the Pareto solutions on an 8-h operation horizon and reducing overall energy costs. While successful, the memetic algorithm is computational expensive which limits its application to building operation decisions on an hourly time scale. To address this challenge, we propose a particle swarm framework, termed augmented multi-objective particle swarm optimization (AMOPSO). The performance of the proposed AMOPSO in terms of solution quality and convergence speed is improved via the fusion of multiple search methods. Extensive experiments are conducted to compare the proposed AMOPSO with nine multi-objective PSO algorithms (MOPSOs) and multi-objective evolutionary algorithms (MOEAs) collected from the literature. Results demonstrate that AMOPSO outperforms the nine state-of-the-art MOPSOs and MOEAs in terms of epsilon, spread, and hypervolume indicator. A building cluster case is then studied to show that the AMOPSO based decision framework is able to make hourly based operation decisions which could significantly improve energy efficiency and achieve more energy cost savings for the smart buildings.     

基于R2指标和参考向量的高维多目标进化算法

在高维多目标优化中, 不同的优化问题存在不同形状的Pareto前沿(PF), 而研究表明大多数多目标进化算法(Multi-objective evolutionary algorithms, MOEAs) 在处理不同的优化问题时普适性较差. 为了解决这个问题, 本文提出了一个基于R2指标和参考向量的高维多目标进化算法(An R2 indicator and reference vector based many-objective optimization evolutionary algorithm, R2-RVEA). R2-RVEA基于Pareto支配选取非支配解来指导种群进化, 仅当非支配解的数量超过种群规模时, 算法进一步采用种群分解策略和R2指标选择策略进行多样性管理. 通过大量的实验证明, 本文提出的算法在处理不同形状的PF时具有良好的性能.     

Hypervolume-based multi-objective local search

This paper presents a multi-objective local search, where the selection is realized according to the hypervolume contribution of solutions. The HBMOLS algorithm proposed is inspired from the IBEA algorithm, an indicator-based multi-objective evolutionary algorithm proposed by Zitzler and Künzli in 2004, where the optimization goal is defined in terms of a binary indicator defining the selection operator. In this paper, we use the indicator optimization principle, and we apply it to an iterated local search algorithm, using hypervolume contribution indicator as selection mechanism. The methodology proposed here has been defined in order to be easily adaptable and to be as parameter-independent as possible. We carry out a range of experiments on the multi-objective flow shop problem and the multi-objective quadratic assignment problem, using the hypervolume contribution selection as well as two different binary indicators which were initially proposed in the IBEA algorithm. Experimental results indicate that the HBMOLS algorithm is highly effective in comparison with the algorithms based on binary indicators.     

DMEA-II: the direction-based multi-objective evolutionary algorithm-II

This paper discusses the use of direction of improvement in guiding multi-objective evolutionary algorithms (MOEAs) during the search process towards the area of Pareto optimal set. We particularly propose a new version of the Direction based Multi-objective Evolutionary Algorithm (DMEA) and name it as DMEA-II. The new features of DMEA-II includes (1) an adaptation of the balance between convergence and spreading by using an adaptive ratio between the convergence and spreading directions being selected over time; (2) a new concept of ray-based density for niching; and (3) a new selection scheme based on the ray-based density for selecting solutions for the next generation. To validate the performance of DMEA-II, we carried out a case study on a wide range of test problems and comparison with other MOEAs. It obtained quite good results on primary performance metrics, namely the generation distance, inverse generation distance, hypervolume and the coverage set. Our analysis on the results indicates the better performance of DMEA-II in comparison with the most popular MOEAs.     

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

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

Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations

This study addresses the resource-constrained project scheduling problem with precedence relations, and aims at minimizing two criteria: the makespan and the total weighted start time of the activities. To solve the problem, five multi-objective metaheuristic algorithms are analyzed, based on Multi-objective GRASP (MOG), Multi-objective Variable Neighborhood Search (MOVNS) and Pareto Iterated Local Search (PILS) methods. The proposed algorithms use strategies based on the concept of Pareto Dominance to search for solutions and determine the set of non-dominated solutions. The solutions obtained by the algorithms, from a set of instances adapted from the literature, are compared using four multi-objective performance measures: distance metrics, hypervolume indicator, epsilon metric and error ratio. The computational tests have indicated an algorithm based on MOVNS as the most efficient one, compared to the distance metrics; also, a combined feature of MOG and MOVNS appears to be superior compared to the hypervolume and epsilon metrics and one based on PILS compared to the error ratio. Statistical experiments have shown a significant difference between some proposed algorithms compared to the distance metrics, epsilon metric and error ratio. However, significant difference between the proposed algorithms with respect to hypervolume indicator was not observed.     

Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front

In evolutionary multi-objective optimization (EMO), the convergence to the Pareto set of a multi-objective optimization problem (MOP) and the diversity of the final approximation of the Pareto front are two important issues. In the existing definitions and analyses of convergence in multi-objective evolutionary algorithms (MOEAs), convergence with probability is easily obtained because diversity is not considered. However, diversity cannot be guaranteed. By combining the convergence with diversity, this paper presents a new definition for the finite representation of a Pareto set, the B-Pareto set, and a convergence metric for MOEAs. Based on a new archive-updating strategy, the convergence of one such MOEA to the B-Pareto sets of MOPs is proved. Numerical results show that the obtained B-Pareto front is uniformly distributed along the Pareto front when, according to the new definition of convergence, the algorithm is convergent.