New fitness sharing approach for multi-objective genetic algorithms

A novel fitness sharing method for MOGA (Multi-Objective Genetic Algorithm) is proposed by combining a new sharing function and sided degradations in the sharing process, with preference to either of two close solutions. The modified MOGA adopting the new sharing approach is named as MOGAS. Three different variants of MOGAS are tested; MOGASc, MOGASp and MOGASd, favoring children over parents, parents over children and solutions closer to the ideal point, respectively. The variants of MOGAS are compared with MOGA and other state-of-the-art multi-objective evolutionary algorithms such as IBEA, HypE, NSGA-II and SPEA2. The new method shows significant performance improvements from MOGA and is very competitive against other Evolutionary Multi-objective Algorithms (EMOAs) for the ZDT and DTLZ test functions with two and three objectives. Among the three variants MOGASd is found to give the best results for the test problems.     

HMOAM: hybrid multi-objective genetic optimization for facial analysis by appearance model

Successful hybridization of single-objective evolutionary algorithm with gradient based methods has shown promising results. However, studies of hybridized Multi-Objective Evolutionary Algorithm are limited, especially in the domain of image analysis. This paper presents a novel methodology of hybridization of multi-objective genetic algorithm for the real world optimization problem of facial analysis of multiple camera images by 2.5D Appearance Model. Facial large lateral movements make acquisition and analysis of facial images by single camera inefficient. Moreover, non-convex multi-dimensional search space formed by the face search by appearance model requires an efficient optimization methodology. Currently, with wide availability of inexpensive cameras, a multi-view system is as practical as a single-view system. To manage these multiple informations, multi-objective genetic algorithm is employed to optimize the face search. To efficiently tackle the problem of non-convexity of the search space, hybridization of NSGA-II (Non-dominated Sorting Genetic Algorithm) with Gradient Descent is proposed in this paper. For this hybridization, we propose a gradient operator in NSGA-II, which computes gradients of the solutions in conjunction with the existing operator of mutation. Thus, it does not increase the computational cost of the system. Another proposition includes a unique method of calculating the relevant information of each camera in a multiple camera system which makes the hybridization procedure efficient and robust. Our proposed algorithm is applied on different facial poses of CMU-PIE database, webcam face images and synthetic face images, and the results are compared with a single view system and a non-hybrid multiple camera system. Simulation results validate the efficiency, accuracy and robustness achieved.     

Multiobjective evolutionary algorithms for complex portfolio optimization problems

This paper investigates the ability of Multiobjective Evolutionary Algorithms (MOEAs), namely the Non-dominated Sorting Genetic Algorithm II (NSGA-II), Pareto Envelope-based Selection Algorithm (PESA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), for solving complex portfolio optimization problems. The portfolio optimization problem is a typical bi-objective optimization problem with objectives the reward that should be maximized and the risk that should be minimized. While reward is commonly measured by the portfolio’s expected return, various risk measures have been proposed that try to better reflect a portfolio’s riskiness or to simplify the problem to be solved with exact optimization techniques efficiently. However, some risk measures generate additional complexities, since they are non-convex, non-differentiable functions. In addition, constraints imposed by the practitioners introduce further difficulties since they transform the search space into a non-convex region. The results show that MOEAs, in general, are efficient and reliable strategies for this kind of problems, and their performance is independent of the risk function used.     

An efficient Differential Evolution based algorithm for solving multi-objective optimization problems

In the present study, a modified variant of Differential Evolution (DE) algorithm for solving multi-objective optimization problems is presented. The proposed algorithm, named Multi-Objective Differential Evolution Algorithm (MODEA) utilizes the advantages of Opposition-Based Learning for generating an initial population of potential candidates and the concept of random localization in mutation step. Finally, it introduces a new selection mechanism for generating a well distributed Pareto optimal front. The performance of proposed algorithm is investigated on a set of nine bi-objective and five tri-objective benchmark test functions and the results are compared with some recently modified versions of DE for MOPs and some other Multi Objective Evolutionary Algorithms (MOEAs). The empirical analysis of the numerical results shows the efficiency of the proposed algorithm.     

A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs

In this paper, we consider the problem of permutation flowshop scheduling with the objectives of minimizing the makespan and total flowtime of jobs, and present a Multi-Objective Simulated-annealing Algorithm (MOSA). Two initial sequences are obtained by using simple and fast existing heuristics, supplemented by the implementation of three improvement schemes. Each of the two resultant sequences corresponds to a possible non-dominated solution containing the minimum value of one objective function. These sequences, taken one at a time, are given as the starting sequences to the MOSA. The MOSA seeks to obtain non-dominated solutions through the implementation of a simple probability function that attempts to generate solutions on the Pareto-optimal front. The probability function selects probabilistically a particular objective function, considering which the algorithm uncovers non-dominated solutions. Moreover, the probability function is varied in such a way that the entire objective-function space is covered uniformly so as to obtain as many non-dominated and well-dispersed solutions as possible. The parameters in the proposed MOSA are determined after conducting a pilot study. Two variants of the proposed algorithm, called MOSA-I and MOSA-II, with different parameter settings with respect to the temperature and epoch length, are considered in the performance evaluation of algorithms. In order to evaluate MOSA-I and MOSA-II, we have made use of 90 benchmark problems provided by Taillard [Eur. J. Operation. Res. 64 (1993) 278]. After an extensive literature survey, the following flowshop multi-objective scheduling algorithms have been identified as benchmark procedures: (a) MOGLS (Multi-Objective Genetic Local Search) by Ishibuchi and Murata [IEEE Trans. Syst., Man, Cybernet. C: Appl. Rev. 28 (1998) 392]; (b) Elitist Non-dominated sorting Genetic Algorithm (ENGA) by Bagchi [Multi-Objective Scheduling by Genetic Algorithms, Kluwer Academic Publishers, 1999]; (c) GPW (Gradual Priority Weighting) approach by Chang, Hsieh and Lin [Int. J. Prod. Econ. 79 (2002) 171]; and (d) a posteriori approach based heuristic by Framinan, Leisten and Ruiz-Usano [Eur. J. Operation. Res. 141 (2002) 559]. The non-dominated sets obtained from each of the existing benchmark algorithms and the proposed MOSA-I and MOSA-II are compared, and subsequently combined to obtain a net non-dominated front. It is found that most of the solutions in the net non-dominated front are yielded by MOSA-I and MOSA-II. In addition, it is noteworthy that both MOSA-I and MOSA-II require less computational effort than the MOGLS, ENGA and GPW.     

Exact hybrid algorithms for solving a bi-objective vehicle routing problem

The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and (2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal solutions of this bi-objective problem. Our approach is based on the adaptive ε-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54 test instances from the TSPLIB are reported.     

A hybrid multi-objective evolutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants

The hot metal is produced from the blast furnaces in the iron plant and should be processed as soon as possible in the subsequent steel plant for energy saving. Therefore, the release times of hot metal have an influence on the scheduling of a steel plant. In this paper, the scheduling problem with release times for steel plants is studied. The production objectives and constraints related to the release times are clarified, and a new multi-objective scheduling model is built. For the solving of the multi-objective optimization, a hybrid multi-objective evolutionary algorithm based on non-dominated sorting genetic algorithm-II (NSGA-II) is proposed. In the hybrid multi-objective algorithm, an efficient decoding heuristic (DH) and a non-dominated solution construction method (NSCM) are proposed based on the problem-specific characteristics. During the evolutionary process, individuals with different solutions may have a same chromosome because the NSCM constructs non-dominated solutions just based on the solution found by DH. Therefore, three operations in the original NSGA-II process are modified to avoid identical chromosomes in the evolutionary operations. Computational tests show that the proposed hybrid algorithm based on NSGA-II is feasible and effective for the multi-objective scheduling with release times.     

Multi-objective optimization for stochastic computer networks using NSGA-II and TOPSIS

Network reliability is a performance indicator of computer/communication networks to measure the quality level. However, it is costly to improve or maximize network reliability. This study attempts to maximize network reliability with minimal cost by finding the optimal transmission line assignment. These two conflicting objectives frustrate decision makers. In this study, a set of transmission lines is ready to be assigned to the computer network, and the computer network associated with any transmission line assignment is regarded as a stochastic computer network (SCN) because of the multistate transmission lines. Therefore, network reliability means the probability to transmit a specified amount of data successfully through the SCN. To solve this multiple objectives programming problem, this study proposes an approach integrating Non-dominated Sorting Genetic Algorithm II (NSGA-II) and Technique for Order Preference by Similarity to Ideal Solution (TOPSIS). NSGA-II searches for the Pareto set where network reliability is evaluated in terms of minimal paths and Recursive Sum of Disjoint Products (RSDP). Subsequently, TOPSIS determines the best compromise solution. Several real computer networks serve to demonstrate the proposed approach.     

基于弹性区带架构的多目标设施布局问题研究

为解决设施面积不等的连续型设施布局问题,建立了基于弹性区带架构布置形式,以物料搬运成本最小、邻近关系最大、距离要求满足度最大的多目标设施布局模型。模型中考虑了区域内的横向、纵向过道,对设施的长宽比进行了限制,使得结果更符合实际情况。为克服传统多目标单一化方法需要人为设置子目标函数权重、主观性过强的缺陷,采用基于带有精英保留策略的非支配排序遗传算法(NSGA Ⅱ)的多目标优化算法求解模型,设计了相应的编码方式、交叉算子、变异算子、罚函数。最后通过某物流园区的实例分析证明了模型与方法的有效性。     

A multi-objective approach for solving a replacement policy problem for equipment subject to imperfect repairs

This paper proposes a multi-objective approach to model a replacement policy problem applicable to equipment with a predetermined period of use (a planning horizon), which may undergo critical and non-critical failures. Corrective replacements and imperfect repairs are taken to restore the system to operation respectively when critical and non-critical failures occur. Generalized Renewal Process (GRP) is used to model imperfect repairs. The proposed model supports decisions on preventive replacement intervals and the number of spare parts purchased at the beginning of the planning horizon. A Multi-Objective Genetic Algorithm (MOGA) coupled with discrete event simulation (DES) is proposed to provide a set of solutions (Pareto-optimum set) committed to the different objectives of a maintenance manager in the face of a replacement policy problem, that is, maintenance cost, rate of occurrence of failures, unavailability, and investment on spare parts. The proposed MOGA is validated by an application example against the results obtained via the exhaustive approach. Moreover, examples are presented to evaluate the behavior of objective functions on Pareto set (trade-off analysis) and the impact of the repair effectiveness on the decision making.     

考虑服务水平的逆向物流网络优化决策

针对电子产品的售后维修服务问题,建立了一个同时考虑成本和服务质量的多目标逆向物流网络优化模型;该问题是多目标的NP-hard问题,应用NSGA-II算法和多目标模拟退火算法(MOSA)两种多目标进化算法,对模型进行求解并对其求解的效果进行比较分析;多组算例测试结果表明,NSGA-II相比MOSA更具优势。     

加工时间可控单机加权总完工时间Pareto优化研究

针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。     

The development of a multi-objective Tabu Search algorithm for continuous optimisation problems

While there have been many adaptations of some of the more popular meta-heuristics for continuous multi-objective optimisation problems, Tabu Search has received relatively little attention, despite its suitability and effectiveness on a number of real-world design optimisation problems. In this paper we present an adaptation of a single-objective Tabu Search algorithm for multiple objectives. Further, inspired by path relinking strategies common in discrete optimisation problems, we enhance our algorithm to allow it to handle problems with large numbers of design variables. This is achieved by a novel parameter selection strategy that, unlike a full parametric analysis, avoids the use of objective function evaluations, thus keeping the overall computational cost of the procedure to a minimum. We assess the performance of our two Tabu Search variants on a range of standard test functions and compare it to a leading multi-objective Genetic Algorithm, NSGA-II. The path relinking-inspired parameter selection scheme gives a clear performance improvement over the basic multi-objective Tabu Search adaptation and both variants perform comparably with the NSGA-II.     

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 hybrid evolutionary algorithm for the job shop scheduling problem

In this paper, a hybrid metaheuristic method for the job shop scheduling problem is proposed. The optimization criterion is the minimization of makespan and the solution method consists of three components: a Differential Evolution-based algorithm to generate a population of initial solutions, a Variable Neighbourhood Search method and a Genetic Algorithm to improve the population; the latter two are interconnected. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches high quality solutions in short computational times using fixed parameter settings.     

Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms

In this work we consider a Transportation Location Routing Problem (TLRP) that can be seen as an extension of the two stage Location Routing Problem, in which the first stage corresponds to a transportation problem with truck capacity. Two objectives are considered in this research, reduction of distribution cost and balance of workloads for drivers in the routing stage. Here, we present a mathematical formulation for the bi-objective TLRP and propose a new representation for the TLRP based on priorities. This representation lets us manage the problem easily and reduces the computational effort, plus, it is suitable to be used with both local search based and evolutionary approaches. In order to demonstrate its efficiency, it was implemented in two metaheuristic solution algorithms based on the Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization (SSPMO) and on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) strategies. Computational experiments showed efficient results in solution quality and computing time.     

SASEGASA: A New Generic Parallel Evolutionary Algorithm for Achieving Highest Quality Results

This paper presents a new generic Evolutionary Algorithm (EA) for retarding the unwanted effects of premature convergence. This is accomplished by a combination of interacting generic methods. These generalizations of a Genetic Algorithm (GA) are inspired by population genetics and take advantage of the interactions between genetic drift and migration. In this regard a new selection scheme is introduced, which is designed to directedly control genetic drift within the population by advantageous self-adaptive selection pressure steering. Additionally this new selection model enables a quite intuitive heuristics to detect premature convergence. Based upon this newly postulated basic principle the new selection mechanism is combined with the already proposed Segregative Genetic Algorithm (SEGA), an advanced Genetic Algorithm (GA) that introduces parallelism mainly to improve global solution quality. As a whole, a new generic evolutionary algorithm (SASEGASA) is introduced. The performance of the algorithm is evaluated on a set of characteristic benchmark problems. Computational results show that the new method is capable of producing highest quality solutions without any problem-specific additions.     

Simulation and multicriteria optimization modeling approach for regional water restoration management

This paper presents a modeling framework that intends to select the optimal robust wastewater reclamation program of measures (PoM) to achieve the European Water Framework Directive (WFD) objectives in the inner Catalonia watersheds. The integrative methodological tool developed incorporates a water quality model to simulate the effects of the PoM used to reduce pollution pressures on the hydrologic network. A Multi-Objective Evolutionary Algorithm (MOEA) helps to identify efficient trade-offs between PoM cost and water quality. Interactive Decisions Map (IDM)—a multi-criteria visualization—based decision support tool is used to provide a clear idea of the trade-off between water status and the cost to achieve such situation. Lastly, a stochastic simulation model to analyze the sensitivity under varied environmental uncertainties is run. Moreover, the tool is oriented to guide water managers in their decision-making processes. Additionally, this paper analyzes the results of the application of the management tool in the inner Catalan watershed in order to perform the European WFD. This tool has had a key role in the design of part of the PoM which shall be implemented to achieve objectives of the WFD in 2015 in all the Catalan catchments.     

Robustness in multi-objective optimization using evolutionary algorithms

This work discusses robustness assessment during multi-objective optimization with a Multi-Objective Evolutionary Algorithm (MOEA) using a combination of two types of robustness measures. Expectation quantifies simultaneously fitness and robustness, while variance assesses the deviation of the original fitness in the neighborhood of the solution. Possible equations for each type are assessed via application to several benchmark problems and the selection of the most adequate is carried out. Diverse combinations of expectation and variance measures are then linked to a specific MOEA proposed by the authors, their selection being done on the basis of the results produced for various multi-objective benchmark problems. Finally, the combination preferred plus the same MOEA are used successfully to obtain the fittest and most robust Pareto optimal frontiers for a few more complex multi-criteria optimization problems.     

A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm

Swarm intelligence is a research branch that models the population of interacting agents or swarms that are able to self-organize. An ant colony, a flock of birds or an immune system is a typical example of a swarm system. Bees’ swarming around their hive is another example of swarm intelligence. Artificial Bee Colony (ABC) Algorithm is an optimization algorithm based on the intelligent behaviour of honey bee swarm. In this work, ABC algorithm is used for optimizing multivariable functions and the results produced by ABC, Genetic Algorithm (GA), Particle Swarm Algorithm (PSO) and Particle Swarm Inspired Evolutionary Algorithm (PS-EA) have been compared. The results showed that ABC outperforms the other algorithms.