求多目标优化问题Pareto最优解集的方法

主要讨论了无约束多目标优化问题Pareto最优解集的求解方法,其中问题的目标函数是C1连续函数.给出了Pareto最优解集的一个充要条件,定义了α强有效解,并结合区间分析的方法,建立了求解无约束多目标优化问题Pareto最优解集的区间算法,理论分析和数值结果均表明该算法是可靠和有效的.     

多目标规划的一种混合遗传算法

本文利用遗传算法的全局搜索内能力及直接搜索算法的局部优化能力，提出了一种用于多目标规划的混合遗传算法．与Pareto遗传算法相比．本文提出的算法能提高多目标遗传算法优化搜索效率，并保证了能得到适舍决策者要求的Pareto最优解．最后，理论与实践证明其有有效性．     

一种求解半向量二层规划问题的基于KKT背离度量方程的粒子群优化算法

下层多目标规划问题的Pareto最优解的精确性对于成功求解半向量二层规划问题具有决定性作用.本文基于多目标规划问题的KKT背离度量方程,设计了具有确定性终止准则的半向量二层规划问题的粒子群算法.最后,利用线性半向量二层规划算例和非线性半向量二层规划算例进行数值仿真,仿真结果表明,算法中的KKT背离度量方程能有效控制下层问题Pareto最优解的精度,从而确保问题最优解的真实有效性.     

改进多目标量子粒子群算法的WSN覆盖及能耗均衡

为了使无线传感器网络的覆盖率和能耗达到最优的效果,提出了一种改进的多目标粒子群优化算法,采用量子粒子群优化更新粒子,利用拥挤距离排序策略,并结合适应度函数值优劣特性对多目标矛盾的性能目标选择,同时通过拥挤距离对加速系数自适应调整提高算法搜索能力,得到了逼近真实前沿的Pareto解集,具有更快的收敛速度和更强的寻优能力.通过对比实验结果表明:提出的算法在解决WSN的多目标优化问题时,能够避免算法陷入局部最优解,更好地平衡网络覆盖和动态通信能耗,使整个网络的综合指数达到了6.249,均明显优于其他三种算法.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

考虑帕累托最优解的多目标优化进化算法

大多数现有的进化算法在处理多目标优化问题(multi-objective optimization problem,MOP)时会遇到Pareto最优解稀疏的困难,特别是当决策变量的数目很大时,如旨在从大量候选特征中找出小部分特征的特征选择.为此,提出了一种求解大规模稀疏MOP的进化算法.算法考虑Pareto最优解的稀疏性,提出了一种新的种群初始化策略和遗传算子,以保证解的稀疏性.此外,还设计了一个测试套件来评估该算法在大规模稀疏MOP中的性能,实验结果和应用实例证明了该算法在处理大规模稀疏MOP问题上的优越性.     

随机混流U型拆卸线平衡排序问题多目标进化算法优化

针对混流U型拆卸线平衡排序问题,考虑拆卸时间不确定,建立了该问题最小拆卸线平均闲置率、尽早拆卸危害和高需求零部件、最小化平均方向改变次数的多目标优化模型,并提出一种基于分解和动态邻域搜索的混合多目标进化算法(Hybrid Multi-objective Evolutionary Algorithm Based on Decomposition,HMOEA/D)。该算法通过采用弹性任务分配策略、动态邻域结构和动态调整权重以保证解的可行性并搜索得到分布较好的非劣解集。最后,仿真求解实验设计技术(DOE)生成的测试算例,结果表明HMOEA/D较其它算法能得到更接近Pareto最优、分布更好的近似解集。     

求解双层规划的多目标布谷鸟算法

双层规划是一类具有主从递阶结构的优化问题,属于NP-hard范畴。本文利用KKT条件将双层规划问题转化为等价的单层约束规划问题,通过约束处理技术进一步转化为带偏好双目标无约束优化问题,提出多目标布谷鸟算法求解策略。该算法采用Pareto支配和ε-个体比较准则,充分利用种群中优秀不可行解的信息指导搜索过程;设置外部档案集存储迭代过程中的优秀个体并通过高斯扰动改善外部档案集的质量,周期性替换群体中的劣势个体,引导种群不断向可行域或最优解逼近。数值实验及其参数分析验证了算法的有效性。     

鲁棒优化中的Pareto有效性

对于一般的不确定优化问题, 研究了鲁棒解的~Pareto 有效性. 首先, 证明了Pareto 鲁棒解集即是鲁棒解集的Pareto 有效集, 因此求Pareto 鲁棒解等价于求鲁棒解集的Pareto 有效元. 其次, 基于推广的epsilon-约束方法, 得到了Pareto 鲁棒解的生成方法.     

多品种柔性生产企业的订单调度模型及其遗传算法

以订单总完工时间最小和订单平均流程时间最小为目标函数,利用改进的多目标遗传算法生成了多品种订单调度模型.为解决组合模型的指数爆炸问题,提出了一种按规则分配订单以及订单中各作业排序相结合的集成调度思想;以一种整数和字母组合的编码方法用于可行解的表达,并在每个分目标的进化过程中,对选择、交叉、变异算子以及精英解保留策略重新进行设计,保证了解的分布性和均匀性;同时还提出了一种新的终止条件,将精英种群与分目标的子种群进行合并,从而加快收敛的速度.以典型的订单生产企业为例进行仿真实验,实验结果表明,应用该算法可以获得满意的Pareto解集.     

Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates

This paper studies the scheduling problem in hybrid flow shop (HFS) environment. The sequence dependent family setup time (SDFST) is concerned with minimization of makespan and total tardiness. Production environments in real world include innumerable cases of uncertainty and stochasticity of events and a suitable scheduling model should consider them. Hence, in this paper, due date is assumed to be uncertain and its data follow a normal distribution. Since the proposed problem is NP-hard, two metaheuristic algorithms are presented based on genetic algorithm, namely: Non-dominated Sorting Genetic Algorithm (NSGAII) and Multi Objective Genetic Algorithm (MOGA). The quantitative and qualitative results of these two algorithms have been compared in different dimensions with multi phase genetic algorithm (MPGA) used in literature review. Experimental results indicate that the NSGAII performs very well when compared against MOGA and MPGA in a considerably shorter time.     

A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming

Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive a dual variant of Benson’s “outer approximation algorithm” to solve multiobjective linear programmes in objective space. We also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight set decomposition. We compare both algorithms on small illustrative and on practically relevant examples.     

An improved simulated annealing algorithm for bandwidth minimization

In this paper, a simulated annealing algorithm is presented for the bandwidth minimization problem for graphs. This algorithm is based on three distinguished features including an original internal representation of solutions, a highly discriminating evaluation function and an effective neighborhood. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of some previous best results.     

An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs

We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can attain. We first show these bounds can be improved if we know more details about the order of some elements of the generating set. Based on these improvements, we present some new families of mixed graphs. For every fixed value of the degree, these families have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal.     

A direct active set algorithm for large sparse quadratic programs with simple bounds

We show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. We propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows us to free more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, we also show how projection techniques can be used to add several constraints to the active set at each iteration. Our experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000.     

Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets

In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time.     

A note on the generalized min-sum set cover problem

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin (STOC 2009). Bansal, Gupta, and Krishnaswamy (SODA 2010) give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements.     

Conical Algorithm in Global Optimization for Optimizing over Efficient Sets

The problem of optimizing some contiuous function over the efficient set of a multiple objective programming problem can be formulated as a nonconvex global optimization problem with special structure. Based on the conical branch and bound algorithm in global optimization, we establish an algorithm for optimizing over efficient sets and discuss about the implementation of this algorithm for some interesting special cases including the case of biobjective programming problems.     

The periodic vehicle routing problem with intermediate facilities

In this paper, we study an extension of the PVRP where the vehicles can renew their capacity at some intermediate facilities. Each vehicle returns to the depot only when its work shift is over. For this problem we propose a tabu search (TS) algorithm and present computational results on a set of randomly generated instances and on a set of PVRP instances taken from the literature.