Multi-objective genetic algorithm and its applications to flowshop scheduling

In this paper, we propose a multi-objective genetic algorithm and apply it to flowshop scheduling. The characteristic features of our algorithm are its selection procedure and elite preserve strategy. The selection procedure in our multi-objective genetic algorithm selects individuals for a crossover operation based on a weighted sum of multiple objective functions with variable weights. The elite preserve strategy in our algorithm uses multiple elite solutions instead of a single elite solution. That is, a certain number of individuals are selected from a tentative set of Pareto optimal solutions and inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply the proposed genetic algorithm to a two-objective function optimization problem with a concave Pareto front. Last, the performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime.     

基于在线感知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解集, 是一种非常有竞争力的方法.     

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.     

混合分解和强度帕累托多目标进化算法

在多目标进化优化中,使用分解策略的基于分解的多目标进化算法(MOEA/D)时间复杂度低,使用〖BP(〗强度帕累托策略的〖BP)〗强度帕累托进化算法-2(SPEA2)能得到分布均匀的解集。结合这两种策略,提出一种新的多目标进化算法用于求解具有复杂、不连续的帕累托前沿的多目标优化问题(MOP)。首先,利用分解策略快速逼近帕累托前沿;然后,利用强度帕累托策略使解集均匀分布在帕累托前沿,利用解集重置分解策略中的权重向量集,使其适配于特定的帕累托前沿;最后,利用分解策略进一步逼近帕累托前沿。使用的反向世代距离(IGD)作为度量标准,将新算法与MOEA/D、SPEA2和paλ-MOEA/D在12个基准问题上进行性能对比。实验结果表明该算法性能在7个基准问题上最优,在5个基准问题上接近于最优,且无论MOP的帕累托前沿是简单或复杂、连续或不连续的,该算法均能生成分布均匀的解集。     

通过网格改进的基于指标的进化算法

设计一种高效的演化多目标优化算法,使其能获得一组同时具有优异的收敛性和多样性的解集是一项很困难的任务。为了能高效求解多目标优化问题,在基于指标的进化算法(IBEA)的基础上：1)引入基于目标空间网格的多样性保持策略,保证算法近似前沿具有优异的分布性;2)引入反向学习机制,同时评估当前解和当前解的反向解,期望能找到一组较优的解从而加快算法收敛。通过6个标准测试函数对改进算法进行测试,其结果表明改进算法可以有效逼近真实Pareto前沿并且分布均匀。     

Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance

Cyclic hoist scheduling problems in automated electroplating lines and surface processing shops attract many attentions and interests both from practitioners and researchers. In such systems, parts are transported from a workstation to another by a material handling hoist. The existing literature mainly addressed how to find an optimal cyclic schedule to minimize the cycle time that measures the productivity of the lines. The material handling cost is an important factor that needs to be considered in practice but seldom addressed in the literature. This study focuses on a biobjective cyclic hoist scheduling problem to minimize the cycle time and the material handling cost simultaneously. We consider the reentrant workstations that are usually encountered in real-life lines but inevitably make the part-flow more complicated. The problem is formulated as a biobjective linear programming model with a given hoist move sequence and transformed into finding a set of Pareto optimal hoist move sequences with respect to the bicriteria. To obtain the Pareto optimal or near-optimal front, a hybrid discrete differential evolution (DDE) algorithm is proposed. In this hybrid evolutional algorithm, the population is divided into several subpopulations according to the maximal work-in-process (WIP) level of the system and the sizes of subpopulations are dynamically adjusted to balance the exploration and exploitation of the search. We propose a constructive heuristic to generate initial subpopulations with different WIP levels, hybrid mutation and crossover operators, an evaluation method that can tackle infeasible individuals and a one-to-one greedy tabu selection method. Computational results on both benchmark instances and randomly generated instances show that our proposed hybrid DDE algorithm outperforms the basic DDE algorithm and can solve larger-size instances than the existing ε-constraint method.     

A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling

Finding feasible scheduling that optimize all objective functions for flexible job shop scheduling problem (FJSP) is considered by many researchers. In this paper, the novel hybrid genetic algorithm and simulated annealing (NHGASA) is introduced to solve FJSP. The NHGASA is a combination of genetic algorithm and simulated annealing to propose the algorithm that is more efficient than others. The three objective functions in this paper are: minimize the maximum completion time of all the operations (makespan), minimize the workload of the most loaded machine and minimize the total workload of all machines. Pareto optimal solution approach is used in NHGASA for solving FJSP. Contrary to the other methods that assign weights to all objective functions to reduce them to one objective function, in the NHGASA and during all steps, problems are solved by three objectives. Experimental results prove that the NHGASA that uses Pareto optimal solutions for solving multi-objective FJSP overcome previous methods for solving the same benchmarks in the shorter computational time and higher quality.     

DEMORS: A hybrid multi-objective optimization algorithm using differential evolution and rough set theory for constrained problems

The aim of this paper is to show how the hybridization of a multi-objective evolutionary algorithm (MOEA) and a local search method based on the use of rough set theory is a viable alternative to obtain a robust algorithm able to solve difficult constrained multi-objective optimization problems at a moderate computational cost. This paper extends a previously published MOEA [Hernández-Díaz AG, Santana-Quintero LV, Coello Coello C, Caballero R, Molina J. A new proposal for multi-objective optimization using differential evolution and rough set theory. In: 2006 genetic and evolutionary computation conference (GECCO’2006). Seattle, Washington, USA: ACM Press; July 2006], which was limited to unconstrained multi-objective optimization problems. Here, the main idea is to use this sort of hybrid approach to approximate the Pareto front of a constrained multi-objective optimization problem while performing a relatively low number of fitness function evaluations. Since in real-world problems the cost of evaluating the objective functions is the most significant, our underlying assumption is that, by aiming to minimize the number of such evaluations, our MOEA can be considered efficient. As in its previous version, our hybrid approach operates in two stages: in the first one, a multi-objective version of differential evolution is used to generate an initial approximation of the Pareto front. Then, in the second stage, rough set theory is used to improve the spread and quality of this initial approximation. To assess the performance of our proposed approach, we adopt, on the one hand, a set of standard bi-objective constrained test problems and, on the other hand, a large real-world problem with eight objective functions and 160 decision variables. The first set of problems are solved performing 10,000 fitness function evaluations, which is a competitive value compared to the number of evaluations previously reported in the specialized literature for such problems. The real-world problem is solved performing 250,000 fitness function evaluations, mainly because of its high dimensionality. Our results are compared with respect to those generated by NSGA-II, which is a MOEA representative of the state-of-the-art in the area.     

Many-objective evolutionary algorithm based on adaptive weighted decomposition

Decomposition is a representative method for handling many-objective optimization problems with evolutionary algorithms. Classical decomposition scheme relies on a set of uniformly distributed reference vectors to divide the objective space into multiple subregions. This scheme often works poorly when the problem has an irregular Pareto front due to the inconsistency between the distribution of reference vectors and the shape of Pareto fronts. We propose in this paper an adaptive weighted decomposition based many-objective evolutionary algorithm to tackle complicated many-objective problems whose Pareto fronts may or may not be regular. Unlike traditional decomposition based algorithms that use a pre-defined set of reference vectors, the reference vectors in the proposed algorithm are produced from the population during the search. The experiments show that the performance of the proposed algorithm is competitive with other state-of-the-art algorithms and is less-sensitive to the irregularity of the Pareto fronts.     

Evolutionary robustness analysis for multi-objective optimization: benchmark problems

This paper presents a new approach to robustness analysis in multi-objective optimization problems aimed at obtaining the most robust Pareto front solutions and distributing the solutions along the most robust regions of the optimal Pareto set. A new set of test problems accounting for the different types of robustness cases is presented in this study. Non-dominated solutions are classified according to their degree of robustness and are distributed along the Pareto front according to specific algorithm parameter values. Verification of the proposed method is carried out using the developed test problems and artificial and real world benchmark test problems present in the literature.     

Multiobjective Evolutionary Algorithm With Controllable Focus on the Knees of the Pareto Front

The optimal solutions of a multiobjective optimization problem correspond to a nondominated front that is characterized by a tradeoff between objectives. A knee region in this Pareto-optimal front, which is visually a convex bulge in the front, is important to decision makers in practical contexts, as it often constitutes the optimum in tradeoff, i.e., substitution of a given Pareto-optimal solution with another solution on the knee region yields the largest improvement per unit degradation. This paper presents a selection scheme that enables a multiobjective evolutionary algorithm (MOEA) to obtain a nondominated set with controllable concentration around existing knee regions of the Pareto front. The preference-based focus is achieved by optimizing a set of linear weighted sums of the original objectives, and control of the extent of the focus is attained by careful selection of the weight set based on a user-specified parameter. The fitness scheme could be easily adopted in any Pareto-based MOEA with little additional computational cost. Simulations on various two- and three-objective test problems demonstrate the ability of the proposed method to guide the population toward existing knee regions on the Pareto front. Comparison with general-purpose Pareto based MOEA demonstrates that convergence on the Pareto front is not compromised by imposing the preference-based bias. The performance of the method in terms of an additional performance metric introduced to measure the accuracy of resulting convergence on the desired regions validates the efficacy of the method.      

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.     

Adaptive weighted-sum method for bi-objective optimization: Pareto front generation

This paper presents a new method that effectively determines a Pareto front for bi-objective optimization with potential application to multiple objectives. A traditional method for multiobjective optimization is the weighted-sum method, which seeks Pareto optimal solutions one by one by systematically changing the weights among the objective functions. Previous research has shown that this method often produces poorly distributed solutions along a Pareto front, and that it does not find Pareto optimal solutions in non-convex regions. The proposed adaptive weighted sum method focuses on unexplored regions by changing the weights adaptively rather than by using a priori weight selections and by specifying additional inequality constraints. It is demonstrated that the adaptive weighted sum method produces well-distributed solutions, finds Pareto optimal solutions in non-convex regions, and neglects non-Pareto optimal solutions. This last point can be a potential liability of Normal Boundary Intersection, an otherwise successful multiobjective method, which is mainly caused by its reliance on equality constraints. The promise of this robust algorithm is demonstrated with two numerical examples and a simple structural optimization problem.     

基于多区域中心点预测的动态多目标优化算法

现实生活中存在很多动态多目标优化问题(DMOPs),这类问题要求算法在环境变化后快速收敛到新的Pareto前沿,并保持解集的多样性,随着Pareto前沿复杂程度的增加,这一问题更加突出.鉴于此,提出一种基于多区域中心点预测的动态多目标优化算法(MCPDMO).首先,根据环境变化的严重程度将种群划分为多个子区域,使得个体的分配更加适应动态变化的环境;然后,分别计算每个子区域的中心点,对不同子区域在不同时刻的中心点建立时间序列,并利用差分模型预测新环境的最优解集,以提高算法对不同环境变化的响应能力;最后,为验证算法的有效性,与3种动态多目标优化算法在10个标准测试函数上进行仿真实验.实验结果表明,所提出算法在具有复杂Pareto前沿的动态问题上表现出更优的收敛性和分布性.     

A New PSO-based Algorithm for Two-Dimensional Non-Guillotine Non-Oriented Cutting Stock Problem

In this paper, a new algorithm is proposed for the two-dimensional non-guillotine non-oriented cutting stock problem. The considered problem consists of cutting small rectangular pieces of predetermined sizes from large but finite rectangular plates. The objective is to generate cutting patterns that minimize the unused area and fulfill customer orders. The proposed algorithm is a combination of a new particle swarm optimization approach with a heuristic criterion inspired from the literature. The algorithm is tested on twenty-two instances divided into two sets. Corresponding results show the algorithm efficiency in optimizing the trim loss that is comprised between 2.6% and 7.8% for all considered instances.     

基于价值修正的圆片下料顺序启发式算法

讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T 型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T 型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。     

Multi-objective sine-cosine algorithm (MO-SCA) for multi-objective engineering design problems

This paper proposes a novel and an effective multi-objective optimization algorithm named multi-objective sine-cosine algorithm (MO-SCA) which is based on the search technique of sine-cosine algorithm (SCA). MO-SCA employs the elitist non-dominated sorting and crowding distance approach for obtaining different non-domination levels and to preserve the diversity among the optimal set of solutions, respectively. The effectiveness of the method is measured by implementing it on multi-objective benchmark problems that have various characteristics of Pareto front such as convex, non-convex and discrete. This proposed algorithm is also checked for the multi-objective engineering design problems with distinctive features. Furthermore, we show the proposed algorithm effectively generates the Pareto front and is easy to implement and algorithmically simple.

     

A Pareto archive particle swarm optimization for multi-objective job shop scheduling

In this paper, we present a particle swarm optimization for multi-objective job shop scheduling problem. The objective is to simultaneously minimize makespan and total tardiness of jobs. By constructing the corresponding relation between real vector and the chromosome obtained by using priority rule-based representation method, job shop scheduling is converted into a continuous optimization problem. We then design a Pareto archive particle swarm optimization, in which the global best position selection is combined with the crowding measure-based archive maintenance. The proposed algorithm is evaluated on a set of benchmark problems and the computational results show that the proposed particle swarm optimization is capable of producing a number of high-quality Pareto optimal scheduling plans.     

一维下料的改进遗传算法优化

针对一维下料优化问题,在对一维下料方案数学模型分析的基础上,提出了基于改进遗传算法的优化求解方案。主要思想是把零件的一个顺序作为一种下料方案,定义了遗传算法中的关键问题:编码、解码方法、遗传算子和适应度函数的定义。该算法设计了一种新颖的遗传算子,包括顺序交叉算子、线性变异算子、扩展选择算子。根据这一算法开发出了一维下料方案的优化系统。实际应用表明,该算法逼近理论最优值,而且收敛速度快,较好地解决了一维下料问题。     

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

多目标优化算法是近年来进化计算研究领域的一个热点,大多数的多目标优化算法试图找到问题的完整的Pareto前沿.然而,随着待优化问题目标个数的增加,算法需要更大的种群规模才能合理地描绘出完整的Pareto前沿.显然这样不仅增加了算法的运行时间,更增加了(决策者)最终解的选择难度.因此,聚焦于搜索Pareto前沿上的特定区...