An experimental analysis of evolutionary heuristics for the biobjective traveling purchaser problem

Given a set of markets and a set of products to be purchased on those markets, the Biobjective Traveling Purchaser Problem (2TPP) consists in determining a route through a subset of markets to collect all products, minimizing the travel distance and the purchasing cost simultaneously. As its single objective version, the 2TPP is an NP-hard Combinatorial Optimization problem. Only one exact algorithm exists that can solve instances up to 100 markets and 200 products and one heuristic approach that can solve instances up to 500 markets and 200 products. Since the Transgenetic Algorithms (TAs) approach has shown to be very effective for the single objective version of the investigated problem, this paper examines the application of these algorithms to the 2TPP. TAs are evolutionary algorithms based on the endosymbiotic evolution and other interactions of the intracellular flow interactions. This paper has three main purposes: the first is the investigation of the viability of Multiobjective TAs to deal with the 2TPP, the second is to determine which characteristics are important for the hybridization between TAs and multiobjective evolutionary frameworks and the last is to compare the ability of multiobjective algorithms based only on Pareto dominance with those based on both decomposition and Pareto dominance to deal with the 2TPP. Two novel Transgenetic Multiobjective Algorithms are proposed. One is derived from the NSGA-II framework, named NSTA, and the other is derived from the MOEA/D framework, named MOTA/D. To analyze the performance of the proposed algorithms, they are compared with their classical counterparts. It is also the first time that NSGA-II and MOEA/D are applied to solve the 2TPP. The methods are validated in 365 uncapacitated instances of the TPPLib benchmark. The results demonstrate the superiority of MOTA/D and encourage further researches in the hybridization of Transgenetic Algorithms and Multiobjective Evolutionary Algorithms specially the ones based on decomposition.     

A novel multi-objective memetic algorithm based on opposition-based self-adaptive differential evolution

Under the framework of evolutionary paradigms, many evolutionary algorithms have been designed for handling multi-objective optimization problems. Each of the different algorithms may display exceptionally good performance in certain optimization problems, but none of them can be completely superior over one another. As such, different evolutionary algorithms are being synthesized to complement each other in view of their strengths and the limitations inherent in them. In this study, the novel memetic algorithm known as the Opposition-based Self-adaptive Hybridized Differential Evolution algorithm (OSADE) is being comprehensively investigated through a comparative study with some state-of-the-art algorithms, such as NSGA-II, non-dominated sorting Differential Evolution (NSDE), MOEA/D-SBX, MOEA/D-DE and the Multi-objective Evolutionary Gradient Search (MO-EGS) by using a suite of different benchmark problems. Through the experimental results that are presented by employing the Inverted Generational Distance (IGD) and the Hausdorff Distance performance indicators, it is seen that OSADE is able to achieve competitive, if not better, performance when compared to the other algorithms in this study.     

A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

A fast steady-state <Emphasis Type="Italic">ε</Emphasis>-dominance multi-objective evolutionary algorithm

Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new ε-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the ε-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, ε-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.     

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.     

A continuation approach to mode-finding of multivariate Gaussian mixtures and kernel density estimates

This paper presents a novel method of multi-objective optimization by learning automata (MOLA) to solve complex multi-objective optimization problems. MOLA consists of multiple automata which perform sequential search in the solution domain. Each automaton undertakes dimensional search in the selected dimension of the solution domain, and each dimension is divided into a certain number of cells. Each automaton performs a continuous search action, instead of discrete actions, within cells. The merits of MOLA have been demonstrated, in comparison with a multi-objective evolutionary algorithm based on decomposition (MOEA/D) and non-dominated sorting genetic algorithm II (NSGA-II), on eleven multi-objective benchmark functions and an optimal problem in the midwestern American electric power system which is integrated with wind power, respectively. The simulation results have shown that MOLA can obtain more accurate and evenly distributed Pareto fronts, in comparison with MOEA/D and NSGA-II.     

A mixture experiments multi-objective hyper-heuristic

This paper proposes a hyper-heuristic that combines genetic algorithm with mixture experiments to solve multi-objective optimisation problems. At every iteration, the proposed algorithm combines the selection criterion (rank indicator) of a number of well-established evolutionary algorithms including NSGA-II, SPEA2 and two versions of IBEA. Each indicator is called according to an associated probability calculated and updated during the search by means of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the maximum (probability distribution) of the surface represented by this model, we also find a good algorithm parameterisation. The design of mixture experiments approach allowed the authors to identify and exploit synergies between the different rank indicators at the different stages of the search. This is demonstrated by our experimental results in which the proposed algorithm compared favourably against other well-established algorithms.     

Research on warehouse design and performance evaluation: A comprehensive review

This paper presents a detailed survey of the research on warehouse design, performance evaluation, practical case studies, and computational support tools. This and an earlier survey on warehouse operation provide a comprehensive review of existing academic research results in the framework of a systematic classification. Each research area within this framework is discussed, including the identification of the limits of previous research and of potential future research directions.     

Evolutionary multiobjective optimization in noisy problem environments

This paper presents a multiobjective evolutionary algorithm (MOEA) capable of handling stochastic objective functions. We extend a previously developed approach to solve multiple objective optimization problems in deterministic environments by incorporating a stochastic nondomination-based solution ranking procedure. In this study, concepts of stochastic dominance and significant dominance are introduced in order to better discriminate among competing solutions. The MOEA is applied to a number of published test problems to assess its robustness and to evaluate its performance relative to NSGA-II. Moreover, a new stopping criterion is proposed, which is based on the convergence velocity of any MOEA to the true Pareto optimal front, even if the exact location of the true front is unknown. This stopping criterion is especially useful in real-world problems, where finding an appropriate point to terminate the search is crucial.     

Synergies from spreadsheet LP used with the theory of constraints—a case study

This paper describes a case study relating to a food-processing plant. The methods used to address the case include spreadsheets combined with Goldratt's Theory of Constraints (TOC), both of which are accessible to practising managers. The paper demonstrates how standard spreadsheet optimisation tools can be used in combination with a TOC framework to provide effective decision aids. The results from the case study indicate real productivity improvements are possible from even small models of a situation. The paper explores the interrelationships and complementaries between Linear Programming and Theory of Constraints frameworks, and details the steps involved in using them in combination. We argue that traditional LP practice should be modified in light of the ease with which LPs can be solved, and suggest that the Theory of Constraints approach provides a useful framework to guide LP use. We share some of the insights gained both by the analysts and by the company.     

A mixed-method optimisation and simulation framework for supporting logistical decisions during offshore wind farm installations

With a typical investment in excess of £100 million for each project, the installation phase of offshore wind farms (OWFs) is an area where substantial cost-reductions can be achieved; however, to-date there have been relatively few studies exploring this. In this paper, we develop a mixed-method framework which exploits the complementary strengths of two decision-support methods: discrete-event simulation and robust optimisation. The simulation component allows developers to estimate the impact of user-defined asset selections on the likely cost and duration of the full or partial completion of the installation process. The optimisation component provides developers with an installation schedule that is robust to changes in operation durations due to weather uncertainties. The combined framework provides a decision-support tool which enhances the individual capability of both models by feedback channels between the two, and provides a mechanism to address current OWF installation projects. The combined framework, verified and validated by external experts, was applied to an installation case study to illustrate the application of the combined approach. An installation schedule was identified which accounted for seasonal uncertainties and optimised the ordering of activities.     

ParEGO extensions for multi-objective optimization of expensive evaluation functions

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.     

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

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

Design of electronic assembly lines: An analytical framework and its application

The design of component assembly lines in Printed Circuit Board (PCB) manufacturing environments is a challenging problem faced by many firms in the electronics industry. The main design approaches to such component assembly lines are the Mini-Line, Flexible Flow Line, and Hybrid Line designs. In this paper, we discuss the operational trade-offs associated with these design alternatives and present a mathematical programming framework that captures relevant system design issues. Each of the design alternatives can be viewed as a special case of the stated mathematical programming model. We develop effective algorithms to solve these mathematical programs. We have used the framework in a specific PCB manufacturing environment to advise managers on the best configuration of their lines. The models were used as sensitivity analysis tools. The results of our computational experiments, combined with qualitative comparisons of different design approaches developed by a crossfunctional team (engineers, manufacturing and product managers), have led to the development of a set of managerial guidelines for the selection of the design plan for component assembly lines in the studied environment.     

Functionality defense through diversity: a design framework to multitier systems

Diversification is one of the most effective approaches to defend multitier systems against attacks, failure, and accidents. However, designing such a system with effective diversification is a challenging task because of stochastic user and attacker behaviors, combinatorial-explosive solution space, and multiple conflicting design objectives. In this study, we present a systematic framework for exploring the solution space, and consequently help the designer select a satisfactory system solution. A simulation model is employed to evaluate design solutions, and an artificial neural network is trained to approximate the behavior of the system based on simulation output. Guided by a trained neural network, a multi-objective evolutionary algorithm (MOEA) is proposed to search the solution space and identify potentially good solutions. Our MOEA incorporates the concept of Herbert Simon??s satisficing. It uses the decision maker??s aspiration levels for system performance metrics as its search direction to identity potentially good solutions. Such solutions are then evaluated via simulation. The newly-obtained simulation results are used to refine the neural network. The exploration process stops when the result converges or a satisfactory solution is found. We demonstrate and validate our framework using a design case of a three-tier web system.     

On interval branch-and-bound for additively separable functions with common variables

Interval branch-and-bound (B&B) algorithms are powerful methods which look for guaranteed solutions of global optimisation problems. The computational effort needed to reach this aim, increases exponentially with the problem dimension in the worst case. For separable functions this effort is less, as lower dimensional sub-problems can be solved individually. The question is how to design specific methods for cases where the objective function can be considered separable, but common variables occur in the sub-problems. This paper is devoted to establish the bases of B&B algorithms for separable problems. New B&B rules are presented based on derived properties to compute bounds. A numerical illustration is elaborated with a test-bed of problems mostly generated by combining traditional box constrained global optimisation problems, to show the potential of using the derived theoretical basis.     

A network equilibrium framework for Internet advertising: Models,qualitative analysis,and algorithms

In this paper, we develop a network equilibrium framework for the modeling and analysis of competitive firms engaged in Internet advertising among multiple websites. The model allows for the determination of both the equilibrium online advertising budget as well as the advertising expenditures on the different websites. We then specialize the model to the case of fixed online budgets for the firms. The governing equilibrium conditions of both models are shown to satisfy finite-dimensional variational inequalities. We present qualitative properties of the solution patterns as well as computational procedures that exploit the underlying abstract network structure of these problems. The models and algorithms are illustrated with numerical examples. This paper adds to the growing literature of the application of network-based techniques derived from operations research to the advertising/marketing arena.     

Designing for Mathematical Abstraction

Our focus is on the design of systems (pedagogical, technical, social) that encourage mathematical abstraction, a process we refer to as designing for abstraction. In this paper, we draw on detailed design experiments from our research on children’s understanding about chance and distribution to re-present this work as a case study in designing for abstraction. Through the case study, we elaborate a number of design heuristics that we claim are also identifiable in the broader literature on designing for mathematical abstraction. Our previous work on the micro-evolution of mathematical knowledge indicated that new mathematical abstractions are routinely forged in activity with available tools and representations, coordinated with relatively na?ve unstructured knowledge. In this paper, we identify the role of design in steering the micro-evolution of knowledge towards the focus of the designer’s aspirations. A significant finding from the current analysis is the identification of a heuristic in designing for abstraction that requires the intentional blurring of the key mathematical concepts with the tools whose use might foster the construction of that abstraction. It is commonly recognized that meaningful design constructs emerge from careful analysis of children’s activity in relation to the designer’s own framework for mathematical abstraction. The case study in this paper emphasizes the insufficiency of such a model for the relationship between epistemology and design. In fact, the case study characterises the dialectic relationship between epistemological analysis and design, in which the theoretical foundations of designing for abstraction and for the micro-evolution of mathematical knowledge can co-emerge.     

Solving multi-objective parallel machine scheduling problem by a modified NSGA-II

In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominated sorting Genetic Algorithm-II (NSGA-II) for a parallel machine scheduling problem with three objectives. The objectives are – (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-II (Non-dominated Sorting Genetic Algorithm–II), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-II as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-II. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-II is observed to perform better than the original NSGA-II. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results.     

A hybrid model based on dynamic programming,neural networks,and surrogate value for inventory optimisation applications

This paper proposes a new approach to minimise inventory levels and their associated costs within large geographically dispersed organisations. For such organisations, attaining a high degree of agility is becoming increasingly important. Linear regression-based tools have traditionally been employed to assist human experts in inventory optimisation; endeavours; recently, Neural Network (NN) techniques have been proposed for this domain. The objective of this paper is to create a hybrid framework that can be utilised for analysis, modelling and forecasting purposes. This framework combines two existing approaches and introduces a new associated cost parameter that serves as a surrogate for customer satisfaction. The use of this hybrid framework is described using a running example related to a large geographically dispersed organisation.