An improved evolutionary algorithm for handling many-objective optimization problems

It has been shown that the multi-objective evolutionary algorithms (MOEAs) act poorly in solving many-objective optimization problems which include more than three objectives. The research emphasis, in recent years, has been put into improving the MOEAs to enable them to solve many-objective optimization problems efficiently. In this paper, we propose a new composite fitness evaluation function, in a novel way, to select quality solutions from the objective space of a many-objective optimization problem. Using this composite function, we develop a new algorithm on a well-known NSGA-II and call it FR-NSGA-II, a fast reference point based NSGA-II. The algorithm is evaluated for producing quality solutions measured in terms of proximity, diversity and computational time. The working logic of the algorithm is explained using a bi-objective linear programming problem. Then we test the algorithm using experiments with benchmark problems from DTLZ family. We also compare FR-NSGA-II with four competitive algorithms from the extant literature to show that FR-NSGA-II will produce quality solutions even if the number of objectives is as high as 20.     

Optimizing a bi-objective multi-product EPQ model with defective items,rework and limited orders: NSGA-II and MOPSO algorithms

In this paper, a bi-objective multi-products economic production quantity (EPQ) model is developed, in which the number of orders is limited and imperfect items that are re-workable are produced. The objectives of the problem are minimization of the total inventory costs as well as minimizing the required warehouse space. The model is shown to be of a bi-objective nonlinear programming type, and in order to solve it two meta-heuristic algorithms namely, the non-dominated sorting genetic algorithm (NSGA-II) and multi-objective particle swarm optimization (MOPSO) algorithm, are proposed. To verify the solution obtained and to evaluate the performance of proposed algorithms, two-sample t-tests are employed to compare the means of the first objective value, the means of the second objective values, and the mean required CPU time of solving the problem using two algorithms. The results show while both algorithms are efficient to solve the model and the solution qualities of the two algorithms do not differ significantly, the computational CPU time of MOPSO is considerably lower than that of NSGA-II.     

A multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a Make-To-Order environment,considering order priority

Nowadays, mixed-model assembly line is used increasingly as a result of customers’ demand diversification. An important problem in this field is determining the sequence of products for entering the line. Before determining the best sequence of products, a new procedure is introduced to choose important orders for entering the shop floor. Thus the orders are sorted using an analytical hierarchy process (AHP) approach based on three criteria: critical ratio of each order (CR_o), Significance degree of customer and innovation in a product, while the last one is presented for the first time. In this research, six objective functions are presented: minimizing total utility work cost, total setup cost and total production rate variation cost are the objectives which were presented previously, another objective is minimizing total idle cost, meanwhile two other new objectives regarding minimizing total operator error cost and total tardiness cost are presented for the first time. The total tardiness cost tries to choose a sequence of products that minimizes the tardiness cost for customers with high priority. First, to check the feasibility of the model, GAMS software is used. In this case, GAMS software could not search all of the solution space, so it is tried in two stages and because this problem is NP-hard, particle swarm optimization (PSO) and simulated annealing (SA) algorithms are used. For small sized problems, to compare exact method with proposed algorithms, the problem must be solved using meta-heuristic algorithms in two stages as GAMS software, whereas for large sized problems, the problem can be solved in two ways (one stage and two stages) by using proposed algorithms; the computational results and pairwise comparisons (based on sign test) show GAMS is a proper software to solve small sized problems, whereas for a large sized problem the objective function is better when solved in one stage than two stages; therefore it is proposed to solve the problem in one stage for large sized problems. Also PSO algorithm is better than SA algorithm based on objective function and pairwise comparisons.     

Overlapping community detection in labeled graphs

We present a new approach for the problem of finding overlapping communities in graphs and social networks. Our approach consists of a novel problem definition and three accompanying algorithms. We are particularly interested in graphs that have labels on their vertices, although our methods are also applicable to graphs with no labels. Our goal is to find k communities so that the total edge density over all k communities is maximized. In the case of labeled graphs, we require that each community is succinctly described by a set of labels. This requirement provides a better understanding for the discovered communities. The proposed problem formulation leads to the discovery of vertex-overlapping and dense communities that cover as many graph edges as possible. We capture these properties with a simple objective function, which we solve by adapting efficient approximation algorithms for the generalized maximum-coverage problem and the densest-subgraph problem. Our proposed algorithm is a generic greedy scheme. We experiment with three variants of the scheme, obtained by varying the greedy step of finding a dense subgraph. We validate our algorithms by comparing with other state-of-the-art community-detection methods on a variety of performance measures. Our experiments confirm that our algorithms achieve results of high quality in terms of the reported measures, and are practical in terms of performance.     

Optimal determination of warranty region for 2D policy: A customers' perspective

Warranty is treated by the manufacturer as a marketing strategy that creates better customer satisfaction, which finally helps to get hold of a bigger market share. The cost incurred towards this service is termed as warranty cost, which is a function of warranty policy and region, product quality and reliability, and the customers' usage pattern. Under the 2D warranty policy, there exists numerous iso-cost regions for any specified value of warranty cost. In this article, we propose a methodology to determine the optimal region when customers' utility is measured by the length of warranty coverage time. It is believed that the results will help the manufacturer to provide improved customer service.     

Hybrid least-squares algorithms for approximate policy evaluation

The goal of approximate policy evaluation is to “best” represent a target value function according to a specific criterion. Different algorithms offer different choices of the optimization criterion. Two popular least-squares algorithms for performing this task are the Bellman residual method, which minimizes the Bellman residual, and the fixed point method, which minimizes the projection of the Bellman residual. When used within policy iteration, the fixed point algorithm tends to ultimately find better performing policies whereas the Bellman residual algorithm exhibits more stable behavior between rounds of policy iteration. We propose two hybrid least-squares algorithms to try to combine the advantages of these algorithms. We provide an analytical and geometric interpretation of hybrid algorithms and demonstrate their utility on a simple problem. Experimental results on both small and large domains suggest hybrid algorithms may find solutions that lead to better policies when performing policy iteration.     

Two new meta-heuristics for a bi-objective supply chain scheduling problem in flow-shop environment

In this study, an integrated multi-objective production-distribution flow-shop scheduling problem will be taken into consideration with respect to two objective functions. The first objective function aims to minimize total weighted tardiness and make-span and the second objective function aims to minimize the summation of total weighted earliness, total weighted number of tardy jobs, inventory costs and total delivery costs. Firstly, a mathematical model is proposed for this problem. After that, two new meta-heuristic algorithms are developed in order to solve the problem. The first algorithm (HCMOPSO), is a multi-objective particle swarm optimization combined with a heuristic mutation operator, Gaussian membership function and a chaotic sequence and the second algorithm (HBNSGA-II), is a non-dominated sorting genetic algorithm II with a heuristic criterion for generation of initial population and a heuristic crossover operator. The proposed HCMOPSO and HBNSGA-II are tested and compared with a Non-dominated Sorting Genetic Algorithm II (NSGA-II), a Multi-Objective Particle Swarm Optimization (MOPSO) and two state-of-the-art algorithms from recent researches, by means of several comparing criteria. The computational experiments demonstrate the outperformance of the proposed HCMOPSO and HBNSGA-II.     

Sequential testing policies for complex systems under precedence constraints

We study the problem of sequentially testing the components of a multi-component system to learn the state of the system, when the tests are subject to precedence constraints and with the objective of minimizing the expected cost of the inspections. Our focus is on k-out-of-n systems, which function if at least k of the n components are functional. A solution is a testing policy, which is a set of decision rules that describe in which order to perform the tests. We distinguish two different classes of policies and describe exact algorithms (one branch-and-bound algorithm and one dynamic program) to find an optimal member of each class. We report on extensive computational experiments with the algorithms for representative datasets.     

Approximation algorithms for the Fault-Tolerant Facility Placement problem

In the Fault-Tolerant Facility Placement problem (FTFP) we are given a set of customers C, a set of sites F, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Each customer j has a demand rj and each site may open an unbounded number of facilities. The objective is to minimize the total cost of opening facilities and connecting each customer j to rj different open facilities. We present two LP-rounding algorithms for FTFP. The first algorithm achieves an approximation ratio of 4. The second algorithm uses the method of filtering to improve the ratio to 3.16.     

基于QFD和双层规划的物流服务供应商选择研究

从物流服务成本和物流服务质量两个方面构建物流服务供应商选择的双层规划模型,上层规划以物流服务成本最小为目标,下层以选择的供应商的综合表现度最大为目标。通过改进QFD模型,将评价指标和客户需求相结合,对待选物流供应商进行综合评价,计算供应商的综合表现度。结合模型的特点设计分层迭代算法,算例验证了模型和算法的有效性。     

An efficient non-dominated sorting method for evolutionary algorithms

We present a new non-dominated sorting algorithm to generate the non-dominated fronts in multi-objective optimization with evolutionary algorithms, particularly the NSGA-II. The non-dominated sorting algorithm used by NSGA-II has a time complexity of O(MN(2)) in generating non-dominated fronts in one generation (iteration) for a population size N and M objective functions. Since generating non-dominated fronts takes the majority of total computational time (excluding the cost of fitness evaluations) of NSGA-II, making this algorithm faster will significantly improve the overall efficiency of NSGA-II and other genetic algorithms using non-dominated sorting. The new non-dominated sorting algorithm proposed in this study reduces the number of redundant comparisons existing in the algorithm of NSGA-II by recording the dominance information among solutions from their first comparisons. By utilizing a new data structure called the dominance tree and the divide-and-conquer mechanism, the new algorithm is faster than NSGA-II for different numbers of objective functions. Although the number of solution comparisons by the proposed algorithm is close to that of NSGA-II when the number of objectives becomes large, the total computational time shows that the proposed algorithm still has better efficiency because of the adoption of the dominance tree structure and the divide-and-conquer mechanism.     

Evolutionary multi criteria design optimization of robot grippers

This paper explores the use of intelligent techniques to obtain optimum geometrical dimensions of a robot gripper. The optimization problem considered is a non-linear, complex, multi-constraint and multicriterion one. Three robot gripper configurations are optimized. The aim is to find Pareto optimal front for a problem that has five objective functions, nine constraints and seven variables. The problem is divided into three cases. Case 1 has first two objective functions, the case 2 considers last three objective functions and case 3 deals all the five objective functions. Intelligent optimization algorithms namely Multi-objective Genetic Algorithm (MOGA), Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) and Multi-objective Differential Evolution (MODE) are proposed to solve the problem. Normalized weighting objective functions method is used to select the best optimal solution from Pareto optimal front. Two multi-objective performance measures (solution spread measure (SSM) and ratio of non-dominated individuals (RNIs)) are used to evaluate the strength of the Pareto optimal fronts. Two more multi-objective performance measures namely optimizer overhead (OO) and algorithm effort are used to find the computational effort of MOGA, NSGA-II and MODE algorithms. The Pareto optimal fronts and results obtained from various techniques are compared and analyzed.     

Evolutionary Minimum Cost Trajectory Planning for Industrial Robots

A general method for computing minimum cost trajectory planning for industrial robot manipulators is presented. The aim is minimization of a cost function with constraints namely joint positions, velocities, jerks and torques by considering dynamic equations of motion. A clamped cubic spline curve is used to represent the trajectory. This is a non-linear constrained optimization problem with five objective functions, 30 constraints and 144 variables. The cost function is a weighted balance of transfer time, mean average of actuators efforts and power, singularity avoidance, joint jerks and joint accelerations. The problem is solved by two evolutionary techniques such as Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) and Differential Evolution (DE). Numerical applications for a six link robotic manipulator – STANFORD robot (pick and place operation) and a two link planar manipulator (motion in the presence of obstacles) are illustrated. The results obtained from the Proposed techniques (NSGA-II and DE) are compared for different values of weighting coefficients. The influences of the algorithm parameters and weight factors on algorithm performance are analyzed. The DE algorithm converges quickly than NSGA-II. Also DE algorithm gives better results than NSGA-II in majority of cases. A comprehensive user-friendly general-purpose software package has been developed using VC++ to obtain the optimal solutions of any complex problem using DE algorithm.     

Convergence analysis of some multiobjective evolutionary algorithms when discovering motifs

An important issue in multiobjective optimization is the study of the convergence speed of algorithms. An optimization problem must be defined as simple as possible to minimize the computational cost required to solve it. In this work, we study the convergence speed of seven multiobjective evolutionary algorithms: DEPT, MO-VNS, MOABC, MO-GSA, MO-FA, NSGA-II, and SPEA2; when solving an important biological problem: the motif discovery problem. We have used twelve instances of four different organisms as benchmark, analyzing the number of fitness function evaluations required by each algorithm to achieve reasonable quality solutions. We have used the hypervolume indicator to evaluate the solutions discovered by each algorithm, measuring its quality every 100 evaluations. This methodology also allows us to study the hit rates of the algorithms over 30 independent runs. Moreover, we have made a deeper study in the more complex instance of each organism. In this study, we observe the increase of the archive (number of non-dominated solutions) and the spread of the Pareto fronts obtained by the algorithm in the median execution. As we will see, our study reveals that DEPT, MOABC, and MO-FA provide the best convergence speeds and the highest hit rates.     

A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem

In this paper, a novel multi-objective location model within multi-server queuing framework is proposed, in which facilities behave as M/M/m queues. In the developed model of the problem, the constraints of selecting the nearest-facility along with the service level restriction are considered to bring the model closer to reality. Three objective functions are also considered including minimizing (I) sum of the aggregate travel and waiting times, (II) maximum idle time of all facilities, and (III) the budget required to cover the costs of establishing the selected facilities plus server staffing costs. Since the developed model of the problem is of an NP-hard type and inexact solutions are more probable to be obtained, soft computing techniques, specifically evolutionary computations, are generally used to cope with the lack of precision. From different terms of evolutionary computations, this paper proposes a Pareto-based meta-heuristic algorithm called multi-objective harmony search (MOHS) to solve the problem. To validate the results obtained, two popular algorithms including non-dominated sorting genetic algorithm (NSGA-II) and non-dominated ranking genetic algorithm (NRGA) are utilized as well. In order to demonstrate the proposed methodology and to compare the performances in terms of Pareto-based solution measures, the Taguchi approach is first utilized to tune the parameters of the proposed algorithms, where a new response metric named multi-objective coefficient of variation (MOCV) is introduced. Then, the results of implementing the algorithms on some test problems show that the proposed MOHS outperforms the other two algorithms in terms of computational time.     

Zen-ReqOptimizer: a search-based approach for requirements assignment optimization

At early phases of a product development lifecycle of large scale Cyber-Physical Systems (CPSs), a large number of requirements need to be assigned to stakeholders from different organizations or departments of the same organization for review, clarification and checking their conformance to standards and regulations. These requirements have various characteristics such as extents of importance to the organization, complexity, and dependencies between each other, thereby requiring different effort (workload) to review and clarify. While working with our industrial partners in the domain of CPSs, we discovered an optimization problem, where an optimal solution is required for assigning requirements to various stakeholders by maximizing their familiarity to assigned requirements, meanwhile balancing the overall workload of each stakeholder. In this direction, we propose a fitness function that takes into account all the above-mentioned factors to guide a search algorithm to find an optimal solution. As a pilot experiment, we first investigated four commonly applied search algorithms (i.e., GA, (1 + 1) EA, AVM, RS) together with the proposed fitness function and results show that (1 + 1) EA performs significantly better than the other algorithms. Since our optimization problem is multi-objective, we further empirically evaluated the performance of the fitness function with six multi-objective search algorithms (CellDE, MOCell, NSGA-II, PAES, SMPSO, SPEA2) together with (1 + 1) EA (the best in the pilot study) and RS (as the baseline) in terms of finding an optimal solution using an real-world case study and 120 artificial problems of varying complexity. Results show that both for the real-world case study and the artificial problems (1 + 1) EA achieved the best performance for each single objective and NSGA-II achieved the best performance for the overall fitness. NSGA-II has the ability to solve a wide range of problems without having their performance degraded significantly and (1 + 1) EA is not fit for problems with less than 250 requirements Therefore we recommend that, if a project manager is interested in a particular objective then (1 + 1) EA should be used; otherwise, NSGA-II should be applied to obtain optimal solutions when putting the overall fitness as the first priority.     

Conjoint-analysis-based multiattribute optimization: application in acoustical design

The concept of customer preference, or product value, prevalent in economics and management science, is just beginning to be used in engineering design. This concept and the associated measurement approaches offer us a theoretically appealing way to aggregating customer preferences for multiple product attributes into a single objective function, representing total product value, which may then be maximized. Among these methods, conjoint analysis has emerged as the most popular approach in marketing to estimate the value that customers attach to different features of a product that can be at different levels. In this paper, we use conjoint analysis in a novel way to assess a product designer’s preferences for addressing a practical problem in acoustical design. We incorporate a designer’s preferences for reducing noise in a curved pressure vessel excited with broadband noise. The shell is part of a large industrial machine. The “product” here refers to a broadband vibration absorber(s) attached to the structure. Through direct interaction with the design engineer, we elicit his/her preferences for various alternative design configurations and specify an aggregate value function. We then apply optimization techniques, interfaced to simulation codes, to maximize the value function. We show that this method provides more economical designs compared to certain conventional formulations. We conclude by summarizing some limitations to this research, which point to several future research opportunities.     

A search based approach to fairness analysis in requirement assignments to aid negotiation, mediation and decision making

This paper uses a multi-objective optimisation approach to support investigation of the trade-offs in various notions of fairness between multiple customers. Results are presented to validate the approach using two real-world data sets and also using data sets created specifically to stress test the approach. Simple graphical techniques are used to visualize the solution space. The paper also reports on experiments to determine the most suitable algorithm for this problem, comparing the results of the NSGA-II algorithms, a widely used multi objective evolutionary algorithm, and the Two-Archive evolutionary algorithm, a recently proposed alternative.     

Evolutionary multi-criteria trajectory modeling of industrial robots in the presence of obstacles

Optimal trajectory planning for robot manipulators is always a hot spot in research fields of robotics. This paper presents two new novel general methods for computing optimal motions of an industrial robot manipulator (STANFORD robot) in presence of obstacles. The problem has a multi-criterion character in which three objective functions, a maximum of 72 variables and 103 constraints are considered. The objective functions for optimal trajectory planning are minimum traveling time, minimum mechanical energy of the actuators and minimum penalty for obstacle avoidance. By far, there has been no planning algorithm designed to treat the objective functions simultaneously. When existing optimization algorithms of trajectory planning tackle the complex instances (obstacles environment), they have some notable drawbacks viz.: (1) they may fail to find the optimal path (or spend much time and memory storage to find one) and (2) they have limited capabilities when handling constraints. In order to overcome the above drawbacks, two evolutionary algorithms (Elitist non-dominated sorting genetic algorithm (NSGA-II) and multi-objective differential evolution (MODE) algorithm) are used for the optimization. Two methods (normalized weighting objective functions method and average fitness factor method) are combinedly used to select best optimal solution from Pareto optimal front. Two multi-objective performance measures (solution spread measure and ratio of non-dominated individuals) are used to evaluate strength of the Pareto optimal fronts. Two more multi-objective performance measures namely optimizer overhead and algorithm effort are used to find computational effort of NSGA-II and MODE algorithms. The Pareto optimal fronts and results obtained from various techniques are compared and analyzed.     

A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem

We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each of them supplying (pickup customer) or demanding (delivery customer) a given amount of a single product. The objective is to design a minimum cost Hamiltonian route for a capacitated vehicle in order to transport the product from the pickup to the delivery customers. The vehicle starts the route from a depot, and its initial load also has to be determined. We propose a hybrid algorithm that combines the GRASP and VND metaheuristics. Our heuristic is compared with other approximate algorithms described in Hernández-Pérez and Salazar-González [Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science 2004;38:245–55]. Computational experiments on benchmark instances reveal that our hybrid method yields better results than the previously proposed approaches.