Search

• A many objective evolutionary algorithm based on decomposition and moth search is proposed. • Random and adaptive weights is used to break the limitation of uniform distribution weights. • Mutual evaluation value is used to evaluate the optimal individual in the neighborhood. • Improving scale factor α in MSA is to improve the performance of the proposed algorithm. Decomposition-based multi-objective evolutionary algorithm (MOEA/D) has good performance in solving multi-objective problems (MOPs) but poor performance in solving many-objective optimization problems (MaOPs). The weight vectors in MOEA/D are relatively fixed, which results in poor performance when dealing with complex MaOPs. In this paper, random and adaptive weights are introduced into MOEA/D to break the limitation of fixed weight vectors. And the moth search algorithm (MSA) is used as an operator to improve global search ability. The updating strategies in MSA are more consistent with the neighborhood learning strategy adopted in MOEA/D. In addition, to enable MSA to find the optimal solution in the neighborhood on the MaOPs to update other individuals. This paper introduces mutual evaluation value for evaluating the optimal individual in the neighborhood, and the proposed algorithm is abbreviated as MOEA/DMS. In comparative experiments on the MaF test suite, hypervolume (HV) and inverted generational distance (IGD) are used to measure MOEA/DMS and other many-objective evolutionary algorithms (MaOEAs). The results show that MOEA/DMS has an excellent performance in dealing with MaOPs. Besides, MOEA/DMS is compared with other state-of-the-art MaOEAs on two combinatorial MaOPs. The results show that MOEA/DMS also has significant advantages in dealing with combinatorial MaOPs. [ABSTRACT FROM AUTHOR]

This paper investigates the influence of adaptive walks heuristics within local searches, by studying to what extent a wiser choice among improving neighbors influences the expected quality of the attained local optima. To this aim, we specifically focus on hill-climbers and introduce the maximum expansion pivoting rule, which selects the improving neighbor having the highest number of improving neighbors. Experiments show that having one step ahead of information allows for wiser neighbor choices, leading to better local optima. As the best improvement climber, a maximum expansion climber selects a particular search trajectory among all possible first improvement trajectories, however, it significantly increases the expected quality of the trajectory. On the other hand, the computational overhead makes this heuristic less valuable when included in an iterated search process, where repeating fast random hill-climbings from random starting points still allows a better exploration of the search space. This paper, therefore, extends previous studies on the relative efficiency of hill-climbing pivoting rules, by focusing on the original maximum expansion selection criterion. Results suggest that the achievement of good local optima combined with the use of approximation techniques and problem specificities could lead to the design of effective advanced metaheuristics that exploit the maximum expansion principle. • Climbers reach high-quality local optima when guided by the expansion score. • The ruggedness levels affect the efficiency of classic selection strategies but not of the maximum expansion. • Approximating the maximum expansion principle significantly reduces the computational cost but achieves good tradeoffs. [ABSTRACT FROM AUTHOR]

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA, one needs to find a way to encode problem constraints into the scheme. In this paper, we propose and discuss several QAOA-based algorithms to solve combinatorial optimization problems with equality and/or inequality constraints. We formalize the encoding method of different types of constraints, and demonstrate the effectiveness and efficiency of the proposed scheme by providing examples and results for some well-known NP optimization problems. Compared to previous constraint-encoding methods, we argue our work leads to a more generalized framework for finding, in the context of QAOA, higher-quality approximate solutions to combinatorial problems with various types of constraints. [ABSTRACT FROM AUTHOR]

Given a simple graph G = (V , E) and a real constant γ ∈ (0 , 1 ] , a γ -clique (or γ -quasi-clique) is a subset V ′ ⊆ V inducing a subgraph with edge density at least γ. The minimum quasi-clique (or γ -clique) partitioning problem (MQCPP) consists in partitioning the vertices of the graph in γ -cliques to minimize the number of elements in the partition. In this paper, we formally introduce the minimum quasi-clique partitioning problem, which has not yet been addressed in the literature from an optimization point of view. We show by using a reduction from the unweighted maximum cut problem that even deciding whether a graph can be partitioned into two γ -cliques is NP-complete. This result contrasts with that of the clique partitioning problem, whose decision version is polynomially solvable for bipartition. We propose four integer programming formulations and a multi-start greedy randomized heuristic to provide initial feasible solutions for MQCPP. Computational experiments show that two formulations that employ the principles of representatives outperform the others regarding the best-obtained solutions and the number of instances solved optimally within the imposed time limit. Furthermore, the results also demonstrate that the instances with medium values of γ are more challenging for the proposed formulations than those with larger or lower values. [ABSTRACT FROM AUTHOR]

• Three models are developed to study simultaneous task and energy planning problem for autonomous vehicles. • A novel neural optimization algorithm using deep reinforcement learning and a link information filter is proposed. • An end-to-end learning framework that directly maps from perceptions to control decisions is proposed. • The proposed neural optimizer can find near-optimal solutions very fast compared to exact and heuristic algorithms. To improve energy awareness of unmanned autonomous vehicles, it is critical to co-optimize task planning and energy scheduling. To the best of our knowledge, most of the existing task planning algorithms either ignore energy constraints or make energy scheduling decisions based on simple rules. To bridge these research gaps, we propose a combinatorial optimization model for the simultaneous task and energy planning (STEP) problem. In this paper, we propose three variants of STEP problems (i) the vehicle can visit stationary charging stations multiple times at various locations; (ii) the vehicle can efficiently coordinate with mobile charging stations to achieve zero waiting time for recharging, and (iii) the vehicle can maximally harvest solar energy by considering time variance in solar irradiance. Besides, in order to obtain fast and reliable solutions to STEP problems, we propose a neural combinatorial optimizer using the deep reinforcement learning algorithm with a proposed link information filter. The near-optimal solutions can be obtained very fast without solving the problem from scratch when environments change. Our simulation results demonstrate that (i) our proposed neural optimizer can find solutions close to the optimum and outperform the exact and heuristic algorithms in terms of computational cost; (ii) the end-to-end learning (directly mapping from perceptions to control) model outperforms the traditional learning (mapping from perception to prediction to control) model. [ABSTRACT FROM AUTHOR]

Abstract This paper focuses on heterogeneous group decision making (GDM) in the setting of incomplete preference relations, including incomplete fuzzy preference relations, incomplete multiplicative preference relations, incomplete additive linguistic preference relations, and incomplete multiplicative linguistic preference relations. Following the consistency-consensus optimization analysis, a new GDM method is proposed which can address inconsistent and incomplete preference relations. Firstly, we consider how to determine unknown information and how to obtain consistent preference relations. In contrast to the existing methods which rank the alternatives from fuzzy preference relations using the additive or multiplicative consistency analysis, this paper follows the consistency level to decide to use the additive or multiplicative consistency. Following the consensus analysis for each type of consistent preference relations, we calculate their comprehensively consistent preference relations and the priority vectors. After that, we build a consistency-based model for calculating the comprehensive priority vector. Furthermore, we offer an ordered position consensus-based method using the built optimization models. The proposed heterogeneous GDM method with incomplete preference relations provides us with a very useful way for dealing with GDM problems in heterogeneous environments. [ABSTRACT FROM AUTHOR]

• Proposes a distributed adaptive optimization spiking neural P system with a distributed population structure and a new adaptive learning rate considering population diversity. • Extensive experiments on knapsack problems show that DAOSNPS gains much better and more stable solutions than OSNPS, AOSNPS and other two optimization algorithms. An optimization spiking neural P system (OSNPS) aims to obtain the approximate solutions of combinatorial optimization problems without the aid of evolutionary operators of evolutionary algorithms or swarm intelligence algorithms. To develop the promising and significant research direction, this paper proposes a distributed adaptive optimization spiking neural P system (DAOSNPS) with a distributed population structure and a new adaptive learning rate considering population diversity. Extensive experiments on knapsack problems show that DAOSNPS gains much better solutions than OSNPS, adaptive optimization spiking neural P system, genetic quantum algorithm and novel quantum evolutionary algorithm. Population diversity and convergence analysis indicate that DAOSNPS achieves a better balance between exploration and exploitation than OSNPS and AOSNPS. [ABSTRACT FROM AUTHOR]

The paper presents a new balanced selection operator applied to the proposed Balanced Non-dominated Tournament Genetic Algorithm (B-NTGA) that actively uses archive to solve multi- and many-objective NP-hard combinatorial optimization problems with constraints. The primary motivation is to make B-NTGA more efficient in exploring Pareto Front Approximation (PFa), focusing on "gaps" and reducing some PFa regions' sampling too frequently. Such a balancing mechanism allows B-NTGA to be more adaptive and focus on less explored PFa regions. The proposed B-NTGA is investigated on two benchmark multi- and many-objective optimization real-world problems, like Thief Traveling Problem and Multi-Skill Resource-Constrained Project Scheduling Problem. The results of experiments show that B-NTGA has a higher efficiency and better performance than state-of-the-art methods. • New balanced GAP selection actively uses archive, focuses on Pareto Front 'gaps' to reduce too frequent sampling of regions. • B-NTGA bases and modifies NTGA2 (i.e., clone elimination, tournament as second selection) and adds balanced GAP selection. • B-NTGA is less time-consuming than NTGA2, uses fewer parameters, and is more efficient than NTGA2. • Experiments for NP-hard multi-objective optimization problems (TTP and MS-RCPSP) comparing B-NTGA to state-of-the-art methods. • Results of experiments showed that B-NTGA is highly effective for multi- and many-objective problems (like TTP and MS-RCPSP). [ABSTRACT FROM AUTHOR]

• A membrane evolution algorithm MEACCP is designed to solve the CCP. • The membranes structure and objects representation of MEACCP are designed. • The population initialization method of MEACCP is designed. • Six evolution operators for membrane structures and their objects are designed. • The solving ability and stability of MEACCP are superior to the comparison algorithms. The Capacitated Clustering Problem (CCP) is a constrained clustering problem with a wide range of applications in VLSI design, vehicle routing, and mail delivery. In order to improve the performance of solving CCP, this paper proposes a membrane evolutionary algorithm MEACCP based on the Membrane Evolutionary Algorithm Framework (MEAF). First, the membrane structure of MEACCP and its object representation are designed. Second, six evolution operators are designed to evolve objects within the membrane and membrane structures. Third, the MEACCP and the method of membrane population initialization are discussed. Finally, MEACCP experiments were conducted on 100 instances of four different types of benchmark datasets, and the experimental results were compared with the results of the current state-of-the-art CCP algorithms. The experimental results show that the number of instances where MEACCP can find the optimal solution is 4.3 ∼ 9.1 times that of the algorithms in comparison, and the stability is better than all comparison algorithms. [ABSTRACT FROM AUTHOR]

• An adaptive and transfer guided metaheuristic is proposed for Evolutionary Multitasking. • Synergies between tasks are analyzed along the search in a dynamic way. • 4 different combinatorial optimization problems have been considered. • 11 multitasking scenarios are solved comprised by 5 to 20 instances. • Proposed AT-MFCGA is compared with MFEA, MFEA-II and MFCGA. Transfer Optimization is an incipient research area dedicated to solving multiple optimization tasks simultaneously. Among the different approaches that can address this problem effectively, Evolutionary Multitasking resorts to concepts from Evolutionary Computation to solve multiple problems within a single search process. In this paper we introduce a novel adaptive metaheuristic algorithm to deal with Evolutionary Multitasking environments coined as Adaptive Transfer-guided Multifactorial Cellular Genetic Algorithm (AT-MFCGA). AT-MFCGA relies on cellular automata to implement mechanisms in order to exchange knowledge among the optimization problems under consideration. Furthermore, our approach is able to explain by itself the synergies among tasks that were encountered and exploited during the search, which helps us to understand interactions between related optimization tasks. A comprehensive experimental setup is designed to assess and compare the performance of AT-MFCGA to that of other renowned Evolutionary Multitasking alternatives (MFEA and MFEA-II). Experiments comprise 11 multitasking scenarios composed of 20 instances of 4 combinatorial optimization problems, yielding the largest discrete multitasking environment solved to date. Results are conclusive in regard to the superior quality of solutions provided by AT-MFCGA with respect to the rest of the methods, which are complemented by a quantitative examination of the genetic transferability among tasks throughout the search process. [ABSTRACT FROM AUTHOR]

• New General Variable Neighborhood Search (GVNS) based heuristic for solving Traveling Repairman Problem with Profits (TRPP). • Extensive comparison of different variants of Variable Neighborhood Descent (VND). • Extensive computational analysis. • 40 out of 60 new best known solutions reported. The Traveling Repairman Problem with profits generalizes the Traveling Repairman Problem, by taking into account the variability of the repairman's profit over different time steps in order to maximize the total profit. In this paper, we first analyze the complexities of several neighborhood structures and the efficient updating of objective values of solutions from those neighborhoods. Then we present a new heuristic based on General variable neighborhood search, that uses a local search that combines those neighborhoods in an effective way. Detailed experiments on benchmark instances show that our new method outperforms all previous heuristics. Out of 60 instances tested, it was able to replicate the best known solutions in 20 of them and find new best solutions in the remaining 40. [ABSTRACT FROM AUTHOR]

The joint order batching and picker routing problem (JOBPRP) is a combinatorial optimization problem that occurs during in the order-picking operation of warehouse management. It consists of simultaneous assignment of customer orders to batches and routing of picking operations in the batches such that the total travel distance is minimized. In this paper, we develop a memetic algorithm with fuzzy-based population control (MA-FPC) to solve the JOBPRP. MA-FPC takes advantage of the hierarchical nature of the problem to design a batch exchange crossover (BEX) operator and a two-level local improvement procedure. BEX transfers complete batches from parent solutions to offsprings. Local improvement systematically employs a combined heuristic and exact routing approach to solve the picker routing problem. Furthermore, fuzzy-based population control is used to dynamically regulate population diversity during the search, which removes individuals from or adds individuals to the population. In numerical experiments, MA-FPC significantly outperforms state-of-the-art point-based and population-based algorithms developed for the order batching problem and JOBPRP with respect to solution quality in reasonable running times. Our algorithm improves the previous best-known solutions for 57 of the 64 benchmark instances. [ABSTRACT FROM AUTHOR]

Many-objective optimization problems abbreviated as MaOPs with more than three objectives have attracted increasing interests due to their widely existing in a variety of real-world applications. This paper presents a novel many-objective population extremal optimization called MaOPEO-HM algorithm for MaOPs by introducing a reference set based many-objective optimization mechanism into a recently developed population extremal optimization framework and designing an adaptive hybrid mutation operation for updating the population. Despite of the successful applications of extremal optimization in different kinds of numerical and engineering optimization problems, it has never been explored to the many-objective optimization domain so far. Because most of the existing many-objective evolutionary algorithms are usually guided by a single mutation operation, which has insufficient ability to exploit the search space of MaOPs and will get stuck at any local efficient front, it is the first attempt to design a novel hybrid mutation scheme in MaOPEO-HM algorithm by combining the advantages of polynomial mutation operator and multi-non-uniform mutation operator effectively. The experiment results for DTLZ test problems with 3, 5, 8, 10, and 15 objectives and WFG test problems with 3, 5, and 8 objectives have demonstrated the superiority of the proposed MaOPEO-HM to five state-of-the-art decomposition-based many-objective evolutionary algorithms including NSGA-III, RVEA, EFR-RR, θ -DEA, and MOEA/DD and two non-decomposition-based algorithms including GrEA and Two_Arch2. Furthermore, the great ability of the designed adaptive hybrid mutation operation incorporated into many-objective population extremal optimization (MaOPEO) has also been illustrated by comparing MaOPEO-HM and two MaOPEO algorithms only based on traditional multi-non-uniform mutation or polynomial mutation for DTLZ problems. [ABSTRACT FROM AUTHOR]

In shape from focus (SFF) methods, the accuracy of the depth map highly depends on the quality of image focus volume. Generally, a linear filtering or averaging using a 2D mask is applied on each slice of the focus volume to filter out the noisy focus measures. This approach may not provide optimal results due to the inherent problems associated with linear filtering. In this paper, the image focus volume is regularized by applying 3D weighted least squares (3D-WLS) approach that enhances the volume to better reconstruct the 3D shape. The weights for the regularization have been computed from the image sequence, and here image sequence acts like a structural prior and guidance volume. Such kind of guided filtering of focus volume has not been carried out earlier. 3D-WLS optimization problem has been solved in an efficient separable manner, such that the solution has been approximated by solving a sequence of 1D linear sub-problems. Sequentially for each dimension, a tridiagonal matrix is used to solve the three-point inhomogeneous Laplacian matrix. Experiments conducted on real and synthetic image sequences demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, a method for optimizing the parameters of multi-objective population-based algorithms is proposed. It is based on a meta-optimization, in which an external algorithm optimizes the parameters of the main algorithm. The purpose of proposed optimization is to select the functions, on the basis of which the values of parameters of the main algorithm are calculated for each algorithm iteration. The assumption was made that the functions should be selected in order to achieve the best possible Pareto front in terms of multi-objective performance metrics. The proposed method has been designed to allow the optimization of any algorithms and thus to avoid the time consuming manual selection of their parameters. To compare the presented method with other approaches, a set of well-known modeling benchmarks were used. [ABSTRACT FROM AUTHOR]

In this paper a novel statistical approach for comparing meta-heuristic stochastic optimization algorithms according to the distribution of the solutions in the search space is introduced, known as extended Deep Statistical Comparison. This approach is an extension of the recently proposed Deep Statistical Comparison approach used for comparing meta-heuristic stochastic optimization algorithms according to the solutions values. Its main contribution is that the algorithms are compared not only according to obtained solutions values, but also according to the distribution of the obtained solutions in the search space. The information it provides can additionally help to identify exploitation and exploration powers of the compared algorithms. This is important when dealing with a multimodal search space, where there are a lot of local optima with similar values. The benchmark results show that our proposed approach gives promising results and can be used for a statistical comparison of meta-heuristic stochastic optimization algorithms according to solutions values and their distribution in the search space. [ABSTRACT FROM AUTHOR]

Highlights • Novel formulation of the column subset selection problem, with regularization term. • Efficient, correct greedy algorithm. • We derive a lower bound for the objective function error. • Remarkable improvements on test data. Improved stability and conditioning. • Good feature choices for clustering even with extremely scarce training data. Abstract The Column Subset Selection Problem is a hard combinatorial optimization problem that provides a natural framework for unsupervised feature selection, and there exist efficient algorithms that provide good approximations. The drawback of the problem formulation is that it incorporates no form of regularization, and is therefore very sensitive to noise when presented with scarce data. In this paper we propose a regularized formulation of this problem, and derive a correct greedy algorithm that is similar in efficiency to existing greedy methods for the unregularized problem. We study its adequacy for feature selection and propose suitable formulations. Additionally, we derive a lower bound for the error of the proposed problems. Through various numerical experiments on real and synthetic data, we demonstrate the significantly increased robustness and stability of our method, as well as the improved conditioning of its output, all while remaining efficient for practical use. [ABSTRACT FROM AUTHOR]

Abstract Organizational innovation requires strong social collaboration and knowledge networks as well as focused partner selection strategies that complement employee strengths. Therefore, this paper proposes an effective, innovative partner selection method on the basis of collaboration network deconstruction optimization using collaboration and knowledge networks. To ensure collaborative network deconstruction optimization, the proposed method firstly improves the focal actor's management efficiency by eliminating network redundancy and identifying the key primary contacts. Then, to fully consider the knowledge benefits to be gained from joint collaboration, the knowledge fusion process is modeled using knowledge combinations from the knowledge networks. Further, social benefits and knowledge benefits maximization are jointly considered in the selection of suitable partners. And at last, a case study is given that demonstrates the proposed method is highly effective in selecting suitable partners for the focal actor that significantly improves both the social and knowledge benefits. [ABSTRACT FROM AUTHOR]

Abstract Some interval-valued intuitionistic fuzzy information MAGDM problems with combinatorial optimization characteristics have so many feasible alternatives that they can hardly be enumerated and evaluated. Moreover, due to the lack of quantitative functions, they are difficult to be solved with traditional combinatorial optimization methods. Therefore, by combining the MAGDM with combinatorial optimization, we propose a decision variable-based combinatorial optimization approach for the purpose of solving the interval-valued intuitionistic fuzzy MAGDM problems in this paper. Firstly, the utility evaluation matrix of decision maker is defined and the interval-valued intuitionistic fuzzy weighted average operator is used to aggregate utility evaluation matrices with decision makers' preference information. Then, the 0–1 integer decision variable is introduced and a combinatorial optimization model is established for the interval-valued intuitionistic fuzzy MAGDM problem. For the purpose of comparison, a multi-attribute decision-making method based on the weighted relative distance is adopted to rank different alternatives. Besides, an artificial bee colony algorithm improved by integer encoding, ranking selection and elite guidance is used to solve the combinatorial optimization model. Finally, two applications of the approach are proposed: research group dispatch and group weapon-group target assignment. Through the comparison of the algorithms, the feasibility of the proposed approach was verified. [ABSTRACT FROM AUTHOR]

Abstract Maintaining population diversity is critical for multi-objective evolutionary algorithms (MOEAs) to solve many-objective optimization problems (MaOPs). Reference vector guided MOEAs have exhibited superiority in handling this issue, where a set of well distributed reference points on a unit hyperplane are generated to construct the reference vectors. Nevertheless, the pre-defined reference vectors could not well handle MaOPs with irregular (e.g., convex, concave, degenerate, and discontinuous) Pareto fronts (PFs). In this paper, we propose two new reference vector adaptation strategies, namely Scaling of Reference Vectors (SRV) and Transformation of Solutions Location (TSL), to handle irregular PFs. Particularly, to solve an MaOP with a convex/concave PF, SRV introduces a specific center vector and adjusts the other reference vectors around it by using a scaling function. TSL transforms the location of well-diversified solutions into a set of new reference vectors to handle degenerate/discontinuous PFs. The two strategies are incorporated into three representative MOEAs based on reference vectors and tested on benchmark MaOPs. The comparison studies with other state-of-the-art algorithms demonstrate the efficiency of the new strategies. [ABSTRACT FROM AUTHOR]

Highlights • The U-curve problem can be used to model feature selection. • We pointed out an error in the first algorithm proposed to solve the U-curve problem. • We introduced UCS, an optimal algorithm for the U-curve problem. • We also provide UCSR, an algorithm for a special case of the U-curve problem. • UCS and UCSR outperformed BFS, CHCGA and SFFS in feature selection experiments. Abstract The U-curve optimization problem is characterized by a decomposable in U-shaped curves cost function over the chains of a Boolean lattice. This problem can be applied to model the classical feature selection problem in Machine Learning. In this paper, we point out that the firstly proposed algorithm to tackle the U-curve problem, the RBM algorithm, is in fact suboptimal. We also present two new algorithms: UCS, which is actually optimal to tackle this problem; and UCSR, a variation of UCS that solves a special case of the U-curve problem and relies on a reduced, ordered binary decision diagram to control the search space. We provide results of two computational assays with these new algorithms: first, W-operator design for filtering of binary images; second, linear SVM design for classification of data sets from the UCI Machine Learning Repository. We show that, in these assays, UCS and UCSR outperformed an exhaustive search and also three widely used heuristics: the SFFS sequential selection, the BFS graph-based search, and the CHCGA genetic algorithm. Finally, we analyze the obtained results and point out improvements that might enhance the performance of these two novel algorithms. [ABSTRACT FROM AUTHOR]

Abstract In this paper, the multi-goal motion planning problem of an environment with some background information about its map is addressed in detail. The motion planning goal is to find a policy in belief space for the robot to traverse through a number of goal points. This problem is modeled as an asymmetric traveling salesman problem (TSP) in the belief space using Partially Observable Markov Decision Process (POMDP) framework. Then, feedback-based information roadmap (FIRM) algorithm is utilized to reduce the computational burden and complexity. By generating a TSP-FIRM graph, the search policy is obtained and an algorithm is proposed for online execution of the policy. Moreover, approaches to cope with challenges such as map updating, large deviations and high uncertainty in localization, which are more troublesome in a real implementation, are carefully addressed. Finally, in order to evaluate applicability and performance of the proposed algorithms, it is implemented in a simulation environment as well as on a physical robot in which some challenges such as kidnapping and discrepancies between real and computational models and map are examined. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we propose a new multiattribute decision making (MADM) method by applying the nonlinear programming (NLP) methodology and particle swarm optimization (PSO) techniques using interval-valued intuitionistic fuzzy values (IVIFVs) to conquer the drawbacks of Chen and Huang's MADM method (2017), which has three drawbacks, i.e., (1) multiple different preference orders (POs) of alternatives are obtained in some situations, (2) the PO of alternatives cannot be distinguished in some circumstances, and (3) the PO of alternatives cannot be obtained in some circumstances. Moreover, the proposed MADM method also can conquer the shortcomings of Chen and Chiou's MADM method (2015), Li's MADM method (2010) and Zhitao and Yingjun's method (2011). [ABSTRACT FROM AUTHOR]

In this paper we present a novel universal metaheuristic, Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA), which is based on the combination of the Bacterial Evolutionary Algorithm and local search techniques, used for solving NP-hard optimization problems. The algorithm was tested on a series of symmetric Traveling Salesman Problems (TSP) and Traveling Salesman Problem with time windows (TSPTW) benchmarks. The size of the symmetric TSP benchmarks went up to 5 000 cities. In all cases the DBMEA algorithm produced optimal or near-optimal solutions and the difference from the known best values was within 0.16%. While for large size problems it was much faster than the Concorde solver, it was found to be slower compared to the Helsgaun-Lin-Kernighan heuristic, which is the most efficient TSP solver method. With some slight modifications the same algorithm was also tested on TSP with time windows (TSPTW) benchmark instances. In most cases the DBMEA procedure found the known best solutions, and it was again the second fastest method compared with the state-of-the-art techniques for the TSPTW. DBMEA is called efficacious because it is a universal method. It can be efficiently applied to various NP-hard optimization problems and, as in all cases, it results in the optimal or a very near-optimal solutions, while its runtime is very predictable in terms of the size of the problem, and the topology of the instance does not affect its runtime significantly. Even though heuristics developed for a particular type of problem might perform better for that restricted class, our novel method proposed here is universally applicable and may be deployed successfully for optimizing other discreet NP-hard graph search and optimization problems as well. [ABSTRACT FROM AUTHOR]

The maximum min-sum dispersion problem (Max-Minsum DP) is an important representative of a large class of dispersion problems. Having numerous applications in practice, the NP-hard Max-Minsum DP is however computationally challenging. This paper introduces an effective solution-based tabu search (SBTS) algorithm for solving the Max-Minsum DP approximately. SBTS is characterized by the joint use of hash functions to determine the tabu status of candidate solutions and a parametric constrained swap neighborhood to enhance computational efficiency. Experimental results on 140 benchmark instances commonly used in the literature demonstrate that the proposed algorithm competes favorably with the state-of-the-art algorithms both in terms of solution quality and computational efficiency. In particular, SBTS improves the best-known results for 80 out of the 140 instances, while matching 51 other best-known solutions. We conduct a computational analysis to identify the respective roles of the hash functions and the parametric constrained swap neighborhood. [ABSTRACT FROM AUTHOR]

Many real-world problems are composed of multiple interacting sub-problems. However, few investigations have been carried out to look into tackling problems from a metaheuristics perspective. The Traveling Thief Problem (TTP) is a new NP-hard problem with two interdependent components that aim to provide a benchmark model to better represent this category of problems. In this paper, TTP is investigated theoretically and empirically. Two algorithms based on a 2-OPT steepest ascent hill climbing algorithm and the simulated annealing metaheuristic named CS2SA* and CS2SA-R are proposed to solve the problem. The obtained results show that the proposed algorithms are efficient for many TTP instances of different sizes and properties and are very competitive in comparison with two of the best-known state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a memetic based framework called Optimized Symmetric Partial Facegraphs (OSPF) to recognize faces prone to adverse conditions such as facial occlusions, expression and illumination variations. Faces are initially segmented into facial components and optimal landmarks are automatically generated by exploiting the bilateral symmetrical property of human faces. The proposed approach combines an improved harmony search algorithm and an intelligent single particle optimizer to take advantage of their global and local search capabilities. Basically, the hybridization version aids to compute the optimal landmarks. These landmarks further serve as the building blocks to intuitively construct the partial facegraphs. The efficiency of the proposed approach has been investigated in addressing the facial occlusion problem when only one exemplar face image per subject is available using comprehensive experimental validations. The proposed approach yields improved recognition rates when compared to recent state-of-the-art techniques. [ABSTRACT FROM AUTHOR]

Many laboratory scale biochemical processes, including clinical diagnostics are being revolutionized by Digital Microfluidic Biochips (DMFBs). This is owing to their high automation capability, low cost, portability, and efficiency. Central to the efficient operation of these devices is the droplet routing problem that aims to drive a set of droplets, each from its source to its target cells, without violating a given set of fluidic and timing constraints. The efficiency of the routing is measured by the amount of cells used and the arrival time of the latest droplet and both criteria are aimed to be minimized simultaneously. To solve this problem we propose an Evolutionary Multi-objective Optimization algorithm for the Droplet Routing problem (EMO-DR) based on the NSGA-II framework, where the crossover operator is not used. EMO-DR features new mutation operators and a biased random generator of initial solutions. Experimental results show that the proposed approach produces competitive results when compared with those obtained through state-of-the-art methods. The paper also highlights the main challenges that evolutionary approaches need to solve when dealing with this routing problem. [ABSTRACT FROM AUTHOR]

The obnoxious p -median problem can be formulated as a constrained binary linear program. It is NP-hard, and has a lot of real world applications. In this paper, a hybrid binary particle swarm optimization is proposed to solve the obnoxious p -median problem. A new position updating rule is presented to inherit the good structure of previous high quality solutions. Furthermore, two tabu based mutation operators are used to avoid the premature convergence and guide the search to a promising area. A greedy repair procedure is developed to repair infeasible solutions. In addition, an iterated greedy local search procedure is utilized to enhance the exploitation ability. Extensive experiments are done on a set of 72 benchmark instances from the literature. Experimental results and comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm. In particular, the proposed algorithm finds new best solutions for 15 instances. Compared with existing algorithms, the proposed algorithm is able to find better average objective function value in a short average computing time. [ABSTRACT FROM AUTHOR]

Using a robustness measure based on values of the polar requirement of amino acids, Freeland and Hurst (1998) showed that less than one in one million random hypothetical codes are better than the standard genetic code. In this paper, instead of comparing the standard code with randomly generated codes, we use an optimisation algorithm to find the best hypothetical codes. This approach has been used before, but considering only one objective to be optimised. The robustness measure based on the polar requirement is considered the most effective objective to be optimised by the algorithm. We propose here that the polar requirement is not the only property to be considered when computing the robustness of the genetic code. We include the hydropathy index and molecular volume in the evaluation of the amino acids using three multi-objective approaches: the weighted formula, lexicographic and Pareto approaches. To our knowledge, this is the first work proposing multi-objective optimisation approaches with a non-restrictive encoding for studying the evolution of the genetic code. Our results indicate that multi-objective approaches considering the three amino acid properties obtain better results than those obtained by single objective approaches reported in the literature. The codes obtained by the multi-objective approach are more robust and structurally more similar to the standard code. [ABSTRACT FROM AUTHOR]

Artificial bee colony (ABC) algorithm, which has explicit strategies to balance intensification and diversification, is a smart swarm intelligence algorithm and was first proposed for continuous optimization problems. In this paper, a hybrid discrete ABC algorithm, which uses acceptance criterion of threshold accepting method, is proposed for Traveling Salesman Problem (TSP). A new solution updating equation, which can learn both from other bees and from features of problem at hand, is designed for the TSP. Aiming to enhance its ability to escape from premature convergence, employed bees and onlooker bees use threshold acceptance criterion to decide whether or not to accept newly produced solutions. Systematic experiments were performed to show the advantage of the new solution updating equation, to verify the necessity of using non-greedy acceptance strategy for keeping sufficient diversity, to compare different selection schemes for onlooker bees, and to analyze the contribution of scout bee. Comparison experiments performed on a wide range of benchmark TSP instances have shown that the proposed algorithm is better than other ABC-based algorithms and is better than or competitive with many other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

The minimum weighted vertex cover (MWVC) problem, an extension of the classical minimum vertex cover (MVC) problem, is an important NP-complete combinatorial optimization problem with a wide range of applications. The objective of this paper is to design an efficient local search algorithm to solve the MWVC problem. First, the weighted edge strategy is proposed to define the dynamic scoring strategy so that our algorithm can find different possible optimal solutions. Second, the weighted configuration checking (WCC) strategy is proposed to overcome the cycling problem in local search. By combining the WCC strategy with the scoring strategy, we design the vertex selection strategy to determine the vertex to be selected as a candidate solution component. Based on these strategies, a novel local search framework, namely diversion local search based on weighted configuration checking (DLSWCC), is presented. DLSWCC is evaluated against several state-of-the-art algorithms on various benchmark instances. Experimental results show that DLSWCC outperforms its competitors in terms of both solution quality and computational efficiency in most classical instances. Specifically, DLSWCC can obtain 22 new upper bounds of 71 moderate-scale problem instances, 5 new upper bounds of 15 large-scale problem instances, and 56 new upper bounds of 56 massive graph instances. [ABSTRACT FROM AUTHOR]

This paper discusses a project selection and adjustment problem in the situation where some project parameters are given by experts’ estimates because of lack of historical data. Uncertain variables are used to describe these project parameters and the use of them is justified. Based on uncertain measure, a cost overrun risk which describes the average amount of investment outlay exceeding the available budget is proposed, and a new optimization model which simultaneously considers the selection of new projects and the adjustment of existing ones is developed. To solve the proposed problem, the deterministic equivalents of the model are provided and a genetic algorithm is offered. As an illustration, an example is also presented and discussed. [ABSTRACT FROM AUTHOR]

In recent years, Cultural Algorithms (CAs) have attracted substantial research interest. When applied to highly multimodal and high dimensional problems, Cultural Algorithms suffer from fast convergence followed by stagnation. This research proposes a novel hybridization between Cultural Algorithms and a modified multiple trajectory search (MTS). In this hybridization, a modified version of Cultural Algorithms is applied to generate solutions using three knowledge sources namely situational knowledge, normative knowledge, and topographic knowledge. From these solutions, several are selected to be used by the modified multi-trajectory search. All solutions generated by both component algorithms are used to update the three knowledge sources in the belief space of Cultural Algorithms. In addition, an adaptive quality function is used to control the number of function evaluations assigned to each component algorithm according to their success rates in the recent past iterations. The function evaluations assigned to Cultural Algorithms are also divided among the three knowledge sources according to their success rates in recent generations of the search. Moreover, the quality function is used to tune the number of offspring these component algorithms are allowed to contribute during the search. The proposed hybridization between Cultural Algorithms and the modified trajectory-based search is employed to solve a test suite of 25 large-scale benchmark functions. The paper also investigates the application of the new algorithm to a set of real-life problems. Comparative studies show that the proposed algorithm can have superior performance on more complex higher dimensional multimodal optimization problems when compared with several other hybrid and single population optimizers. [ABSTRACT FROM AUTHOR]

This paper proposes a novel hybrid shuffled frog leaping algorithm (HSFLA) for vehicle routing problem with time windows (VRPTW). The diversity control strategy is developed to construct the memeplexes of the HSFLA and avoid ending the search prematurely. The modified clone selection procedure is presented to improve the quality of the solutions and bring more diversity to the population. Improved and extended extremal optimization (EO) with alternative move operators is also introduced to the exploitation of the algorithm. Furthermore, the adaptive soft time windows penalty measure is proposed to allow the existence of infeasible solutions in the evolution process. Our approach is estimated and compared with other state-of-the-art heuristics using Solomon and Cordeau VRPTW test sets. The experimental results show that the presented algorithm is very effective for handling VRPTW. [ABSTRACT FROM AUTHOR]

Hyper-heuristics aim to automate the heuristic selection process in order to operate well across different problem instances, or even across different problem domains. A traditional hyper-heuristic framework has two levels, a high level strategy and a set of low level heuristics. The role of the high level strategy is to decide which low level heuristic should be executed at the current decision point. This paper proposes a Monte Carlo tree search hyper-heuristic framework. We model the search space of the low level heuristics as a tree and use Monte Carlo tree search to search through the tree in order to identify the best sequence of low level heuristics to be applied to the current state. To improve the effectiveness of the proposed framework, we couple it with a memory mechanism which contains a population of solutions, utilizing different population updating rules. The generality of the proposed framework is demonstrated using the six domains of the hyper-heuristic competition (CHeSC) test suite (boolean satisfiability (MAX-SAT), one dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman and vehicle routing with time windows). The results demonstrate that the proposed hyper-heuristic generalizes well over all six domains and obtains competitive, if not better results, when compared to the best known results that have previously been presented in the scientific literature. [ABSTRACT FROM AUTHOR]

Solving constraint satisfaction problems via constraint programming involves the exploration of a search tree where the potential solutions are distributed. The exploration phase is essentially controlled by an enumeration strategy that decides the order in which variables and values are selected to verify its feasibility. This process is known to be quite important, indeed perfect enumerations can reach a solution without useless explorations. However, selecting good strategies in advance is quite hard as the effects along the search are often unpredictable. Autonomous search addresses this concern by proposing to replace on the fly bad-performing strategies by more promising ones. Strategies are selected from a quality rank which is generated in function of their performance on the current solving process. However, the ranking computation is commonly tuned by an optimizer that negatively impacts the performance of the whole resolution. In this paper, we propose a faster autonomous search approach by integrating a powerful database technique called skyline. This technique allows us to avoid the use of costly rank functions and optimizers, accelerating as a consequence the solving process. We report results where the skyline-based approach clearly competes with previously reported autonomous search frameworks as well as with classic and more sophisticated heuristics such as impact-based search and dom / wdeg . [ABSTRACT FROM AUTHOR]

The paper aims at designing new strategies to extend the selection step of traditional Differential Evolution for Multi-objective Optimization algorithm to proficiently obtain Pareto-optimal solutions in presence of noise. The first strategy, referred to as adaptive selection of sample size, is employed to balance the trade-off between accurate fitness estimate and computational complexity. The second strategy is concerned with determining defuzzified centroid value of the noisy fitness samples, instead of their conventional averaging, as the fitness measure of the trial solutions. The third extension is concerned with the introduction of a probabilistic Pareto ranking strategy to tarnish the detrimental effect of noise incurred in deterministic selection of traditional algorithms. The fourth strategy attempts to extend Goldberg’s approach to examine possible placement of a slightly inferior solution in the optimal Pareto front using a more statistically viable comparator. Finally, to ensure the diversity in distribution of quality solutions in the noisy fitness landscapes, a new selection criterion induced by the crowding distance measure and the probability of dominance is formulated. Experiments undertaken to study the performance of the extended algorithm reveal that the extended algorithm outperforms its competitors with respect to four performance metrics, when examined on a test-suite of 23 standard benchmarks with additive noise of three statistical distributions. [ABSTRACT FROM AUTHOR]

The maximally diverse grouping problem requires finding a partition of a given set of elements into a fixed number of mutually disjoint subsets (or groups) in order to maximize the overall diversity between elements of the same group. In this paper we develop a new variant of variable neighborhood search for solving the problem. The extensive computational results show that our new heuristic significantly outperforms the current state of the art. Moreover, the best known solutions have been improved on 531 out of 540 test instances from the literature. [ABSTRACT FROM AUTHOR]

Capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning that is classified as an NP-Hard problem. The aim is to determine where to locate facilities and how to move commodities such that the customers' demands are satisfied and the total cost minimized. In this paper, a new hybrid optimization method called Hybrid Evolutionary Firefly-Genetic Algorithm is proposed, which is inspired by social behavior of fireflies and the phenomenon of bioluminescent communication. The method combines the discrete Firefly Algorithm (FA) with the standard Genetic Algorithm (GA). It is devoted to the detailed description of the problem, and an adaption of the algorithm. Computational results on random generated problems consisting of 2000 locations and 2000 customers are reported. [ABSTRACT FROM AUTHOR]