A multi-objective and evolutionary hyper-heuristic applied to the Integration and Test Order Problem

The field of Search-Based Software Engineering (SBSE) has widely utilized Multi-Objective Evolutionary Algorithms (MOEAs) to solve complex software engineering problems. However, the use of such algorithms can be a hard task for the software engineer, mainly due to the significant range of parameter and algorithm choices. To help in this task, the use of Hyper-heuristics is recommended. Hyper-heuristics can select or generate low-level heuristics while optimization algorithms are executed, and thus can be generically applied. Despite their benefits, we find only a few works using hyper-heuristics in the SBSE field. Considering this fact, we describe HITO, a Hyper-heuristic for the Integration and Test Order Problem, to adaptively select search operators while MOEAs are executed using one of the selection methods: Choice Function and Multi-Armed Bandit. The experimental results show that HITO can outperform the traditional MOEAs NSGA-II and MOEA/DD. HITO is also a generic algorithm, since the user does not need to select crossover and mutation operators, nor adjust their parameters.     

Choice function based hyper-heuristics for multi-objective optimization

A selection hyper-heuristic is a high level search methodology which operates over a fixed set of low level heuristics. During the iterative search process, a heuristic is selected and applied to a candidate solution in hand, producing a new solution which is then accepted or rejected at each step. Selection hyper-heuristics have been increasingly, and successfully, applied to single-objective optimization problems, while work on multi-objective selection hyper-heuristics is limited. This work presents one of the initial studies on selection hyper-heuristics combining a choice function heuristic selection methodology with great deluge and late acceptance as non-deterministic move acceptance methods for multi-objective optimization. A well-known hypervolume metric is integrated into the move acceptance methods to enable the approaches to deal with multi-objective problems. The performance of the proposed hyper-heuristics is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, they are applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the non-deterministic move acceptance, particularly great deluge when used as a component of a choice function based selection hyper-heuristic.     

Elite-guided multi-objective artificial bee colony algorithm

Multi-objective optimization has been a difficult problem and a research focus in the field of science and engineering. This paper presents a novel multi-objective optimization algorithm called elite-guided multi-objective artificial bee colony (EMOABC) algorithm. In our proposal, the fast non-dominated sorting and population selection strategy are applied to measure the quality of the solution and select the better ones. The elite-guided solution generation strategy is designed to exploit the neighborhood of the existing solutions based on the guidance of the elite. Furthermore, a novel fitness calculation method is presented to calculate the selecting probability for onlookers. The proposed algorithm is validated on benchmark functions in terms of four indicators: GD, ER, SPR, and TI. The experimental results show that the proposed approach can find solutions with competitive convergence and diversity within a shorter period of time, compared with the traditional multi-objective algorithms. Consequently, it can be considered as a viable alternative to solve the multi-objective optimization problems.     

Convergence analysis of a self-adaptive multi-objective evolutionary algorithm based on grids

Evolutionary algorithms have been successfully applied to various multi-objective optimization problems. However, theoretical studies on multi-objective evolutionary algorithms, especially with self-adaption, are relatively scarce. This paper analyzes the convergence properties of a self-adaptive (μ+1)-algorithm. The convergence of the algorithm is defined, and general convergence conditions are studied. Under these conditions, it is proven that the proposed self-adaptive (μ+1)-algorithm converges in probability or almost surely to the Pareto-optimal front.     

多目标函数优化的元胞蚂蚁算法

提出一种求解多目标函数优化的元胞蚂蚁算法．该方法将元胞自动机演化规则引入蚂蚁算法,给出了在连续空间多目标函数优化的算法描述,定义了与蚂蚁信息素释放有关的元胞演化规则及蚂蚁邻域的转移概率,并实现了算法的具体步骤．在Matlab环境下,采用该算法对一些典型的测试函数进行求解和验证．实验结果表明,该方法具有向真实的Pareto前沿逼近的效果,是一种求解多目标优化的有效方法．     

Non-additive multi-objective robot coalition formation

Manifold increase in the complexity of robotic tasks has mandated the use of robotic teams called coalitions that collaborate to perform complex tasks. In this scenario, the problem of allocating tasks to teams of robots (also known as the coalition formation problem) assumes significance. So far, solutions to this NP-hard problem have focused on optimizing a single utility function such as resource utilization or the number of tasks completed. We have modeled the multi-robot coalition formation problem as a multi-objective optimization problem with conflicting objectives. This paper extends our recent work in multi-objective approaches to robot coalition formation, and proposes the application of the Pareto Archived Evolution Strategy (PAES) algorithm to the coalition formation problem, resulting in more efficient solutions. Simulations were carried out to demonstrate the relative diversity in the solution sets generated by PAES as compared to previously studied methods. Experiments also demonstrate the relative scalability of PAES. Finally, three different selection strategies were implemented to choose solutions from the Pareto optimal set. Impact of the selection strategies on the final coalitions formed has been shown using Player/Stage.     

Plateaus can be harder in multi-objective optimization

In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.     

A multi-objective evolutionary algorithm to exploit the similarities of resource allocation problems

The complexity of a resource allocation problem (RAP) is usually NP-complete, which makes an exact method inadequate to handle RAPs, and encourages heuristic techniques to this class of problems for obtaining approximate solutions in polynomial time. Different heuristic techniques have already been investigated for handling various RAPs. However, since the properties of an RAP can help in characterizing other RAPs, instead of individual solution techniques, the similarities of different RAPs might be exploited for developing a common solution technique for them. Two RAPs of quite different nature, namely university class timetabling and land-use management, are considered here for such a study. The similarities between the problems are first explored, and then a common multi-objective evolutionary algorithm (a kind of heuristic techniques) for them is developed by exploiting those similarities. The algorithm is problem-dependent to some extent and can easily be extended to other similar RAPs. In the present work, the algorithm is applied to two real instances of the considered problems, and its properties are derived from the obtained results.     

A multi-objective evolutionary algorithm for examination timetabling

This paper considers the scheduling of exams for a set of university courses. The solution to this exam timetabling problem involves the optimization of complete timetables such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as seating capacity and no overlapping exams. To solve such a multi-objective combinatorial optimization problem, this paper presents a multi-objective evolutionary algorithm that uses a variable-length chromosome representation and incorporates a micro-genetic algorithm and a hill-climber for local exploitation and a goal-based Pareto ranking scheme for assigning the relative strength of solutions. It also imports several features from the research on the graph coloring problem. The proposed algorithm is shown to be a more general exam timetabling problem solver in that it does not require any prior information of the timetable length to be effective. It is also tested against a few influential and recent optimization techniques and is found to be superior on four out of seven publicly available datasets.     

A robust scheduling method based on a multi-objective immune algorithm

A robust scheduling method is proposed to solve uncertain scheduling problems. An uncertain scheduling problem is modeled by a set of workflow models, and then a scheduling scheme (solution) of the problem can be evaluated by workflow simulations executed with the workflow models in the set. A multi-objective immune algorithm is presented to find Pareto optimal robust scheduling schemes that have good performance for each model in the set. The two optimization objectives for scheduling schemes are the indices of the optimality and robustness of the scheduling results. An antibody represents a resource allocation scheme, and the methods of antibody coding and decoding are designed to deal with resource conflicts during workflow simulations. Experimental tests show that the proposed method can generate a robust scheduling scheme that is insensitive to uncertain scheduling environments.     

Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front

In evolutionary multi-objective optimization (EMO), the convergence to the Pareto set of a multi-objective optimization problem (MOP) and the diversity of the final approximation of the Pareto front are two important issues. In the existing definitions and analyses of convergence in multi-objective evolutionary algorithms (MOEAs), convergence with probability is easily obtained because diversity is not considered. However, diversity cannot be guaranteed. By combining the convergence with diversity, this paper presents a new definition for the finite representation of a Pareto set, the B-Pareto set, and a convergence metric for MOEAs. Based on a new archive-updating strategy, the convergence of one such MOEA to the B-Pareto sets of MOPs is proved. Numerical results show that the obtained B-Pareto front is uniformly distributed along the Pareto front when, according to the new definition of convergence, the algorithm is convergent.     

Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems

The offline 2D bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem in which objects with various width and length sizes are packed into minimized number of 2D bins. Various versions of this well-known industrial engineering problem can be faced frequently. Several heuristics have been proposed for the solution of 2DBPP but it has not been possible to find the exact solutions for large problem instances. Next fit, first fit, best fit, unified tabu search, genetic and memetic algorithms are some of the state-of-the-art methods successfully applied to this important problem. In this study, we propose a set of novel hyper-heuristic algorithms that select/combine the state-of-the-art heuristics and local search techniques for minimizing the number of 2D bins. The proposed algorithms introduce new crossover and mutation operators for the selection of the heuristics. Through the results of exhaustive experiments on a set of offline 2DBPP benchmark problem instances, we conclude that the proposed algorithms are robust with their ability to obtain high percentage of the optimal solutions.     

A self-organized speciation based multi-objective particle swarm optimizer for multimodal multi-objective problems

This paper proposes a self-organized speciation based multi-objective particle swarm optimizer (SS-MOPSO) to locate multiple Pareto optimal solutions for solving multimodal multi-objective problems. In the proposed method, the speciation strategy is used to form stable niches and these niches/subpopulations are optimized to search and maintain Pareto-optimal solutions in parallel. Moreover, a self-organized mechanism is proposed to improve the efficiency of the species formulation as well as the performance of the algorithm. To maintain the diversity of the solutions in both the decision and objective spaces, SS-MOPSO is incorporated with the non-dominated sorting scheme and special crowding distance techniques. The performance of SS-MOPSO is compared with a number of the state-of-the-art multi-objective optimization algorithms on fourteen test problems. Moreover, the proposed SS-MOSPO is also employed to solve a real-life problem. The experimental results suggest that the proposed algorithm is able to solve the multimodal multi-objective problems effectively and shows superior performance by finding more and better distributed Pareto solutions.     

一种子群体个数动态变化的多目标优化协同进化算法

给出一种新型的在多目标优化条件下的进化算法群体停滞判别准则,并基于该准则提出一种合作型多目标优化协同进化算法．该算法在运行过程中自适应地决定子群体的新增和灭绝．使得子群体个数依据需要动态变化,减小了对计算资源的消耗,并解决了对复杂多目标优化问题难以事先进行分解的问题．对所提算法的计算复杂度进行了理论分析,并把它与已有的多目标进化算法进行了比较,结果表明所提算法具有较高的搜索性能．     

Dynamic multi-objective evolutionary algorithms for single-objective optimization

This paper proposes a new method for handling the difficulty of multi-modality for the single-objective optimization problem (SOP). The method converts a SOP to an equivalent dynamic multi-objective optimization problem (DMOP). A new dynamic multi-objective evolutionary algorithm (DMOEA) is implemented to solve the DMOP. The DMOP has two objectives: the original objective and a niche-count objective. The second objective aims to maintain the population diversity for handling the multi-modality difficulty during the search process. Experimental results show that the performance of the proposed algorithm is significantly better than the state-of-the-art competitors on a set of benchmark problems and real world antenna array problems.     

A mathematical framework for passenger screening optimization via a multi-objective evolutionary approach

Concerns regarding the smuggling of dangerous items into commercial flights escalated after the failed Christmas day bomber attack. As a result, the Transportation Security Agency (TSA) has strengthened its efforts to detect passengers carrying hazardous items by installing novel screening technologies and by increasing the number of random pat-downs performed at security checkpoints nationwide. However, the implementation of such measures has raised privacy and health concerns among different groups thus making the design and evaluation of new inspection strategies strongly necessary. This research presents a mathematical framework to design passenger inspection strategies that include the utilization of novel and traditional technologies (i.e. body scanners, explosive detection systems, explosive trace detectors, walk-through metal detectors, and wands) offered by multiple manufacturers, to identify three types of items: metallic, bulk explosives (i.e. plastic, liquids, gels), and traces of explosives. A multiple objective optimization model is proposed to optimize inspection security, inspection cost, and processing time; an evolutionary approach is used to solve the model. The result is a Pareto set of quasi-optimal solutions representing multiple inspection strategies. Each strategy is different in terms of: (1) configuration, (2) the screening technologies included, (3) threshold calibration, and consequently, (4) inspection security, inspection cost, and processing time.     

An evolutionary approach for multi-objective vehicle routing problems with backhauls

The vehicle routing problem (VRP) is an important aspect of transportation logistics with many variants. This paper studies the VRP with backhauls (VRPB) in which the set of customers is partitioned into two subsets: linehaul customers requiring a quantity of product to be delivered, and backhaul customers with a quantity to be picked up. The basic VRPB involves finding a collection of routes with minimum cost, such that all linehaul and backhaul customers are serviced. A common variant is the VRP with selective backhauls (VRPSB), where the collection from backhaul customers is optional. For most real world applications, the number of vehicles, the total travel cost, and the uncollected backhauls are all important objectives to be minimized, so the VRPB needs to be tackled as a multi-objective problem. In this paper, a similarity-based selection evolutionary algorithm approach is proposed for finding improved multi-objective solutions for VRPB, VRPSB, and two further generalizations of them, with fully multi-objective performance evaluation.     

A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem

In this paper, a mixed-model assembly line (MMAL) sequencing problem is studied. This type of production system is used to manufacture multiple products along a single assembly line while maintaining the least possible inventories. With the growth in customers’ demand diversification, mixed-model assembly lines have gained increasing importance in the field of management. Among the available criteria used to judge a sequence in MMAL, the following three are taken into account: the minimization of total utility work, total production rate variation, and total setup cost. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional approaches. Therefore, a hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and bacteria optimization (BO) are deployed. The performance of the proposed hybrid algorithm is then compared with three well-known genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed hybrid algorithm outperforms the existing genetic algorithms, significantly in large-sized problems.     

A genetic algorithm for a bi-objective capacitated arc routing problem

The capacitated arc routing problem (CARP) is a very hard vehicle routing problem for which the objective—in its classical form—is the minimization of the total cost of the routes. In addition, one can seek to minimize also the cost of the longest trip.In this paper, a multi-objective genetic algorithm is presented for this more realistic CARP. Inspired by the second version of the Non-dominated sorted genetic algorithm framework, the procedure is improved by using good constructive heuristics to seed the initial population and by including a local search procedure. The new framework and its different flavour is appraised on three sets of classical CARP instances comprising 81 files.Yet designed for a bi-objective problem, the best versions are competitive with state-of-the-art metaheuristics for the single objective CARP, both in terms of solution quality and computational efficiency: indeed, they retrieve a majority of proven optima and improve two best-known solutions.     

A multi-objective routing algorithm for Wireless Multimedia Sensor Networks

In this paper, a new multi-objective approach for the routing problem in Wireless Multimedia Sensor Networks (WMSNs) is proposed. It takes into account Quality of Service (QoS) requirements such as delay and the Expected Transmission Count (ETX). Classical approximations optimize a single objective or QoS parameter, not taking into account the conflicting nature of these parameters which leads to sub-optimal solutions. The case studies applying the proposed approach show clear improvements on the QoS routing solutions. For example, in terms of delay, the approximate mean improvement ratios obtained for scenarios 1 and 2 were of 15 and 28 times, respectively.