The bilevel optimization problem is a kind of commonly existing optimization problem, which includes a nested lower-level optimization problem as a constraint condition. The nested lower-level optimization problem should be solved with every upper-level decision fixed as a parameter. Consequently, it is usually computationally very expensive to solve bilevel optimization problems. In this paper, we propose a bilevel evolutionary algorithm based on upper-level-driven lower-level search (BLEA-UDLS). Driven by the upper-level optimization, the lower-level search in BLEA-UDLS is carried out on some upper-level superior solutions rather than equally and indiscriminately on all solutions, which makes sure that the front solutions of the population have more accurate lower-level decisions and saves lots of evaluation budgets on less important solutions. In the lower-level search, the lower-level decisions of different solutions are optimized cooperatively with the computation resources dynamically adjusted, where more computation resources are assigned for less explored solutions. Compared with some other bilevel evolutionary algorithms, the experimental results have confirmed the effectiveness of the proposed BLEA-UDLS for solving BLOPs and meanwhile saving evaluation budgets.

Class imbalance and noisy data widely exist in real-world problems, and the support vector machine (SVM) is hard to construct good classifiers on these data. Fuzzy SVMs (FSVMs), as variants of SVM, use a fuzzy membership function both to reflect the samples’ importance and to remove the impact of noises, and employ cost-sensitive technology to address the class imbalance. They can handle the noise and class imbalance problems in many cases; however, the fuzzy membership functions are often affected by the class imbalance data, leading to inaccurate measures for samples’ performance and affecting the performance of FSVMs. To solve this problem, we design a new fuzzy membership function and combine it with cost-sensitive learning to deal with the class imbalance problem with noisy data, named Slack-Factor-based FSVM (SFFSVM). In SFFSVM, the relative distances between samples and an estimated hyperplane, called slack factors, are used to define the fuzzy membership function. To eliminate the impact of class imbalance on the function and gain more accurate samples’ importance, we rectify the importance according to the positional relationship between the estimated hyperplane and the optimal hyperplane of the problem, and the slack factors of samples. Comprehensive experiments on artificial and real-world datasets demonstrate that SFFSVM outperforms other comparative methods on F1, MCC, and AUC-PR metrics.

Imbalanced data clustering is a challenging problem in machine learning. The main difficulty is caused by the imbalance in both cluster size and data density distribution. To address this problem, we propose a novel clustering algorithm called LDPI based on local-density peaks in this study. First, an initial sub-cluster construction scheme is designed based on a 3-dimensional (3-D) decision graph that can easily detect the initial sub-cluster centers and identify the noise points. Second, a sub-cluster updating strategy is designed, which can automatically identify the false sub-cluster centers and update the initial sub-clusters. Third, a sub-cluster merging scheme is designed, which merges the updated initial sub-clusters into final clusters. Consequently, the proposed algorithm has three advantages: 1) It does not require any input parameters; 2) It can automatically determine the cluster centers and number of clusters; 3) It is suitable for imbalanced datasets and datasets with arbitrary shapes and distributions. The effectiveness of LDPI is demonstrated experimentally and the superiority of LDPI is identified by comparison with 5 state-of-the-art algorithms.

It is a key issue to find out all longest common subsequences of multiple sequences over a set of finite alphabets, namely MLCS problem, in computational biology, pattern recognition and information retrieval, to name a few. However, it is very challenging to tackle the large-scale MLCS problem effectively and efficiently due to the high complexity of time and space. To this end, this paper will therefore propose a Branch Elimination based Space and Time efficient algorithm called BEST-MLCS, which includes the following four key strategies: 1) Estimation scheme for the lower bound of the length of MLCS. 2) Estimation scheme for the upper bound of the length of the paths through the current node. 3) Branch elimination strategy by finding all useless match points and removing the branches not on the longest paths. 4) A new Directed Acyclic Graph (DAG) construction method for constructing the smallest DAG among the existing ones. As a result, the proposed algorithm BEST-MLCS can save a lot of space and time and can handle much larger scale MLCS problems than the existing algorithms. Extensive experiments conducted on biological DNA sequences show that the performance of the proposed algorithm BEST-MLCS outperforms three state-of-the-art algorithms in terms of run-time and memory consumption.

Searching Longest Common Subsequences (LCS) of Multi-ple (i.e., three or more) sequences, denoted as MLCS for short, is a fundamental problem in computational biology, pattern recognition, file comparison and information retrieval, to name a few. Basically, an MLCS problem is more challenging than the LCS of two sequences which can be solved by a dynamic programming (DP) method whose running time and memory space are both$O(n^{2})$, where$n$is the length of the sequences.

The search space of large-scale multi-objective optimization problems (LSMOPs) is huge because of the hundreds or even thousands of decision variables involved. It is very challenging to design efficient algorithms for LSMOPs to search the whole space effectively and balance the convergence and diversity at the same time. In this paper, to tackle this challenge, we develop a new algorithm based on a weighted optimization framework with two effective strategies. The weighted optimization framework transforms an LSMOP into multiple small-scale multi-objective optimization problems based on a problem transformation mechanism to reduce the dimensionality of the search space effectively. To further improve its effectiveness, we firstly propose a centerline symmetry strategy to select reference solutions to transform the LSMOPs. It takes not only some non-dominated solutions but also their centerline symmetric points as the reference solutions, which can enhance the population diversity to avoid the algorithm falling into local minima. Then, a new double-line transformation function is designed to expand the search range of the transformed problem to further improve the convergence and diversity. With the two strategies, more widely distributed potential search areas are provided and the optimal solutions can be found easier. To demonstrate the effectiveness of our proposed algorithm, numerical experiments on widely used benchmarks are executed and the statistical results show that our proposed algorithm is more competitive and performs better than the other state-of-the-art algorithms for solving LSMOPs.

Designing efficient algorithms for the large-scale multi-objective problems (LSMOPs) is a very challenging problem currently. To tackle LSMOPs, we first design a new reference points selection strategy to enhance the diversity of algorithms and avoid the algorithm falling into local minima. The strategy selects not only a part of nondominated solutions with the largest crowding distance, but also a part of relatively uniformly distributed solutions as the reference points. In this way, much better diversity and convergence can be obtained. Second, we propose a direction-guided offspring generation strategy, where a type of potential directions is designed to generate the promising solutions which can balance the convergence and diversity of the obtained solutions and improve the effectiveness of the algorithm significantly. Based on the two proposed strategies, we propose a new effective algorithm for LSMOPs. Numerical experiments are executed on two widely used large-scale multi-objective benchmark problem sets with 200, 500 and 1000 decision variables and a comparison with five state-of-the-art algorithms is made. The experimental results show that our proposed algorithm is effective and can obtain significantly better solutions than the compared algorithms.

In this paper, we propose a new method for large scale multi-objective optimization based on symmetric points search and variable grouping, named SSVG. The main idea is to use variable grouping scheme first to divide the original decision space into several subspaces. In each subspace, the symmetric points of the points in population form some potential search directions. Using the search directions, the possibility of finding the optimal solutions will increase greatly. Moreover, in order to decrease the dimension of problem, a new transformation function which transforms the decision space into a lower dimension search space (weight vector space) is designed. Furthermore, experiments are conducted on some benchmarks with 200, 500 and 1000 decision variables and the proposed algorithm SSVG is compared with three state-of-the-art algorithms: MOEA/DVA, WOF and LSMOF. The results show that the proposed algorithm outperforms the compared algorithms in term of convergence and diversity.

MOTIVATION: Multiple longest common subsequence (MLCS) problem is searching all longest common subsequences of multiple character sequences. It appears in many fields such as data mining, DNA alignment, bioinformatics, text editing and so on. With the increasing in sequence length and number of sequences, the existing dynamic programming algorithms and the dominant point-based algorithms become ineffective and inefficient, especially for large-scale MLCS problems. RESULTS: In this paper, by considering the characteristics of DNA sequences with many consecutively repeated characters, we first design a character merging scheme which merges the consecutively repeated characters in the sequences. As a result, it shortens the length of sequences considered and saves the space of storing all sequences. To further reduce the space and time costs, we construct a weighted directed acyclic graph which is much smaller than widely used directed acyclic graph for MLCS problems. Based on these techniques, we propose a fast and memory efficient algorithm for MLCS problems. Finally, the experiments are conducted and the proposed algorithm is compared with several state-of-the art algorithms. The experimental results show that the proposed algorithm performs better than the compared state-of-the art algorithms in both time and space costs. AVAILABILITY AND IMPLEMENTATION: https://www.ncbi.nlm.nih.gov/nuccore and https://github.com/liusen1006/MLCS.

MOTIVATION: Searching the Longest Common Subsequences of many sequences is called a Multiple Longest Common Subsequence (MLCS) problem which is a very fundamental and challenging problem in many fields of data mining. The existing algorithms cannot be applicable to problems with long and large-scale sequences due to their huge time and space consumption. To efficiently handle large-scale MLCS problems, a Path Recorder Directed Acyclic Graph (PRDAG) model and a novel Path Recorder Algorithm (PRA) are proposed. RESULTS: In PRDAG, we transform the MLCS problem into searching the longest path from the Directed Acyclic Graph (DAG), where each longest path in DAG corresponds to an MLCS. To tackle the problem efficiently, we eliminate all redundant and repeated nodes during the construction of DAG, and for each node, we only maintain the longest paths from the source node to it but ignore all non-longest paths. As a result, the size of the DAG becomes very small, and the memory space and search time will be greatly saved. Empirical experiments have been performed on a standard benchmark set of both DNA sequences and protein sequences. The experimental results demonstrate that our model and algorithm outperform the related leading algorithms, especially for large-scale MLCS problems. AVAILABILITY AND IMPLEMENTATION: This program code is written by the first author and can be available at https://www.ncbi.nlm.nih.gov/nuccore and https://blog.csdn.net/wswguilin. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Currently, there are four drawbacks for filled function methods: (1) too many local optimal solutions result in huge difficulty to search global optimal solutions; (2) difficult to control the parameter(s); (3) difficult to determine the initial point for minimization of filled function; (4) the shallow basins will affect the solution precision during the minimization of the filled function. To overcome these drawbacks, in this paper, we adopt a flatten function to eliminate many local optimal solutions first, and then a new filled function with one parameter is proposed, and its parameter is easy to control. Furthermore, we propose an efficient method for determining initial point of the filled function by using adaptive step size. Moreover, when some basins of the filled function are shallow ones, it will result in inefficiency of searching these basins during the minimization of the filled function. To tackle this issue and make the search for global optimal solutions much easier, we propose a strategy of basin deepening. By integrating these schemes, we propose a new efficient filled flatten function method. Numerical results indicate the efficiency and effectiveness of the proposed filled function methods.

Many real-world problems contain a large number of decision variables which can be modeled as large scale global optimization (LSGO) problems. One effective way to solve an LSGO problem is to decompose it into smaller subproblems to solve. The existing works mainly focused on designing methods to decompose separable problems, while seldom focused on the decomposition of nonseparable large scale problems. Also, the existing decomposition methods only learn the interaction (correlation or interdependence) among variables to make the decomposition. In this article, we make the decomposition deeper: we not only consider the variable interaction but also take the essentialness of the variable into account to form a deep grouping method. To do this, we first design an essential/trivial variable detection scheme to support the deep decomposition for both separable problems and nonseparable problems. Based on it, we propose a new decomposition method called deep grouping method. Then, we design a new differential evolution (DE) algorithm with a new mutation strategy. By integrating all these, we propose a hybrid deep grouping (HDG) algorithm. Finally, the experiments are conducted on the widely used and most challenging LSGO benchmark suites, and the comparison results of the proposed algorithm with the state-of-the-art algorithms indicate the proposed algorithm is more effective.

The performance of the traditional Pareto-based evolutionary algorithms sharply reduces for many-objective optimization problems, one of the main reasons is that Pareto dominance could not provide sufficient selection pressure to make progress in a given population. To increase the selection pressure toward the global optimal solutions and better maintain the quality of selected solutions, in this paper, a new dominance method based on expanding dominated area is proposed. This dominance method skillfully combines the advantages of two existing popular dominance methods to further expand the dominated area and better maintain the quality of selected solutions. Besides, through dynamically adjusting its parameter with the iteration, our proposed dominance method can timely adjust the selection pressure in the process of evolution. To demonstrate the quality of selected solutions by our proposed dominance method, the experiments on a number of well-known benchmark problems with 5–25 objectives are conducted and compared with that of the four state-of-the-art dominance methods based on expanding dominated area. Experimental results show that the new dominance method not only enhances the selection pressure but also better maintains the quality of selected solutions.

Decomposition-based evolutionary algorithms have shown great potential in many-objective optimization. However, the lack of theoretical studies on decomposition methods has hindered their further development and application. In this paper, we first theoretically prove that weight sum, Tchebycheff, and penalty boundary intersection decomposition methods are essentially interconnected. Inspired by this, we further show that highly customized dominance relationship can be derived from decomposition for any given decomposition vector. A new evolutionary algorithm is then proposed by applying the customized dominance relationship with adaptive strategy to each subpopulation of multiobjective to multiobjective framework. Experiments are conducted to compare the proposed algorithm with five state-of-the-art decomposition-based evolutionary algorithms on a set of well-known scaled many-objective test problems with 5 to 15 objectives. Simulation results have shown that the proposed algorithm can make better use of the decomposition vectors to achieve better performance. Further investigations on unscaled many-objective test problems verify the robust and generality of the proposed algorithm.

Multi-Installment Divisible-Load Scheduling model is a hot topic in the field of Big Data Processing in heterogeneous parallel and distributed systems. The effective division of data and the determination of scheduling strategy are the key and difficult problems. Minimizing the make-span of the entire divisible load is the primary objective of multi-installment scheduling in heterogeneous parallel and distributed systems. It has been demonstrated that the make-span is minimized when the processor sequence follows the order in which the link speed decrease in single-installment scheduling, however, the optimization of multi-installment divisible-load scheduling is a very hard problem. The descending order of link speeds is usually not an optimal order. To solve this problem, we propose a multi-installment scheduling model considering the processor order, and design an efficient global optimization genetic algorithm to solve the model. Experimental results show that the proposed algorithm has better performance than that of the compared multi-Installment methods.

In view of the shortcomings that many clustering algorithms such as K-means clustering algorithm are not suitable for the non-convex dataset and the Affinity Propagation (AP) algorithm may cluster two adjacent different class points into one class, we proposed a new clustering algorithm by using boundary information. The idea of the proposed algorithm in this paper is as follows: First, use the number of points contained in each point's neighborhood as its density, and consider the points whose density are below the average density as boundary points. Then, count the number of boundary points. If the number of boundary points is larger than a given threshold then clustering is carried out by transfer ideas directly, otherwise boundary points will be regarded as the cluster boundary wall. When the boundary points are encountered in the transitive clustering process, the transfer stopped and selected an unprocessed non-boundary point to start clustering process as above again until all non-boundary points are processed, so as to effectively prevent clustering two adjacent different class points into one class. Because of the clustering of transfer idea, the proposed algorithm is applicable to nonconvex datasets, and different clustering schemes are adopted according to the number of boundary points which increases the applicability of the algorithm. Experimental results on synthetic datasets and standard datasets show that the algorithm proposed in this paper is efficient.

For a large-scale global optimization (LSGO) problem, divide-and-conquer is usually considered an effective strategy to decompose the problem into smaller subproblems, each of which can then be solved individually. Among these decomposition methods, variable grouping is shown to be promising in recent years. Existing variable grouping methods usually assume the problem to be black-box (i.e., assuming that an analytical model of the objective function is unknown), and they attempt to learn appropriate variable grouping that would allow for a better decomposition of the problem. In such cases, these variable grouping methods do not make a direct use of the formula of the objective function. However, it can be argued that many real-world problems are white-box problems, that is, the formulas of objective functions are often known a priori. These formulas of the objective functions provide rich information which can then be used to design an effective variable group method. In this article, a formula-based grouping strategy (FBG) for white-box problems is first proposed. It groups variables directly via the formula of an objective function which usually consists of a finite number of operations (i.e., four arithmetic operations “[Formula: see text]”, “[Formula: see text]”, “[Formula: see text]”, “[Formula: see text]” and composite operations of basic elementary functions). In FBG, the operations are classified into two classes: one resulting in nonseparable variables, and the other resulting in separable variables. In FBG, variables can be automatically grouped into a suitable number of non-interacting subcomponents, with variables in each subcomponent being interdependent. FBG can easily be applied to any white-box problem and can be integrated into a cooperative coevolution framework. Based on FBG, a novel cooperative coevolution algorithm with formula-based variable grouping (so-called CCF) is proposed in this article for decomposing a large-scale white-box problem into several smaller subproblems and optimizing them respectively. To further enhance the efficiency of CCF, a new local search scheme is designed to improve the solution quality. To verify the efficiency of CCF, experiments are conducted on the standard LSGO benchmark suites of CEC'2008, CEC'2010, CEC'2013, and a real-world problem. Our results suggest that the performance of CCF is very competitive when compared with those of the state-of-the-art LSGO algorithms.

Multi-string matching (MSM) is a core technique searching a text string for all occurrences of some string patterns. It is widely used in many applications. However, as the number of string patterns increases, most of the existing algorithms suffer from two issues: the long matching time, and the high memory consumption. To address these issues, in this paper, a fast matching engine is proposed for large-scale string matching problems. Our engine includes a filter module and a verification module. The filter module is based on several bitmaps which are responsible for quickly filtering out the invalid positions in the text, while for each potential matched position, the verification module confirms true pattern occurrence. In particular, we design a compact data structure called Adaptive Matching Tree (AMT) for the verification module, in which each tree node only saves some pattern fragments of the whole pattern set and the inner structure of each tree node is chosen adaptively according to the features of the corresponding pattern fragments. This makes the engine time and space efficient. The experiments indicate that, our matching engine performs better than the compared algorithms, especially for large pattern sets.

The scheduling for divisible load in heterogeneous distributed system is a well known NP-hard problem. The problem is even more complex and challenging when its model has more than one objective, The difficulty is to satisfy multiple objectives that may be of conflicting nature. This paper investigates a multi-objective scheduling problem for divisible load in heterogeneous distributed systems. First, the cost of the system is taken into account and its quantitative formula is given. Second, a bi-objective optimization model, which minimizes the cost of system and the makespan of the load, is established. For the sake of solving the bi-objective optimization model efficiently, a novel effective bi-objective genetic algorithm combing the idea of MOEA/D is proposed. Finally, numerical simulation experiments are conducted, and the experimental results indicate that the effectiveness of the proposed model and algorithm.

Information usually can be abstracted as a character sequence over a finite alphabet. With the advent of the era of big data, the increasing length and size of the sequences from various application fields (e.g., biological sequences) result in the classical NP-hard problem, searching for the Multiple Longest Common Subsequences of multiple sequences (i.e., MLCS problem with many applications in the areas of bioinformatics, computational genomics, pattern recognition, etc.), becoming a research hotspot and facing severe challenges. In this paper, we firstly reveal that the leading dominant-point-based MLCS algorithms are very hard to apply to long and large-scale sequences alignments. To overcome their defects, based on the proposed problem-solving model and parallel topological sorting strategies, we present a novel efficient parallel MLCS algorithm. The comprehensive experiments on the benchmark datasets of both random and biological sequences demonstrate that both the time and space complexities of the proposed algorithm are only linearly related to the dominants from aligned sequences, and that the proposed algorithm greatly outperforms the existing state-of-the-art dominant-point-based MLCS algorithms, and hence it is very suitable for long and large-scale sequences alignments.

The Linked Open Data (LOD) community effort is a cornerstone in the realization of the Semantic Web vision [1]. However, since an instance in the LOD is likely to be denoted with many identifiers (e.g., URIs) by different parties, instance coreference resolution, which identifies different identifiers for the same instance and eliminates the inconsistency between the datasets, has become critical to the development of LOD.

The cooperative co-evolution framework (CC) is widely used in the large scale global optimization. It is believed that the CC framework is very sensitive to grouping strategies and the performance deteriorate if interacted variables are not correctly grouped. So many efforts have been devoted to find good ways to correctly decompose the large scale problem into smaller sub-problems so as to effectively solve the original problem by optimizing these smaller sub-problems using a search algorithm. However, what is the relationship between the grouping strategy and the search algorithm adopted in CC? what is the effect of grouping strategies on the CC framework? This work will tackle these issues. We try to unveil the impact of different grouping strategies on CC and the relationship between the grouping strategies and the search algorithms by empirical study. The experiment results show that the correct result of variable grouping is very important since it can turn the large scale problem into smaller sub-problems and make the problem solving easier. It indeed has a big influence on the results obtained by the search algorithm. However, when the search algorithm adopted is not suitable or effective, even if the grouping strategy gives the correct grouping results, the final results may be poor. In this case, grouping strategy only plays little role on the CC. Thus, only effective grouping strategy plus efficient search algorithm can result in good solutions for large global optimization problems.

The Suffix Array (SA) is a fundamental data structure which is widely used in the applications such as string matching, text index and computation biology, etc. How to sort the suffixes of a string in lexicographical order is a primary problem in constructing SAs, and one of the widely used suffix sorting algorithms is qsufsort. However, qsufsort suffers one critical limitation that the order of suffixes starting with the same [Formula: see text] characters cannot be determined in the kth round. To this point, in our paper, an efficient suffix sorting algorithm called dsufsort is proposed by overcoming the drawback of the qsufsort algorithm. In particular, our proposal maintains the depth of each unsorted portion of SA, and sorts the suffixes based on the depth in each round. By this means, some suffixes that cannot be sorted by qsufsort in each round can be sorted now, as a result, more sorting results in current round can be utilized by the latter rounds and the total number of sorting rounds will be reduced, which means dsufsort is more efficient than qsufsort. The experimental results show the effectiveness of the proposed algorithm, especially for the text with high repetitions.

The weighted sum of objective functions is one of the simplest fitness functions widely applied in evolutionary algorithms (EAs) for multiobjective programming. However, EAs with this fitness function cannot find uniformly distributed solutions on the entire Pareto front for nonconvex and complex multiobjective programming. In this paper, a novel EA based on adaptive multiple fitness functions and adaptive objective space division is proposed to overcome this shortcoming. The objective space is divided into multiple regions of about the same size by uniform design, and one fitness function is defined on each region by the weighted sum of objective functions to search for the nondominated solutions in this region. Once a region contains fewer nondominated solutions, it is divided into several sub-regions and one additional fitness function is defined on each sub-region. The search will be carried out simultaneously in these sub-regions, and it is hopeful to find more nondominated solutions in such a region. As a result, the nondominated solutions in each region are changed adaptively, and eventually are uniformly distributed on the entire Pareto front. Moreover, the complexity of the proposed algorithm is analyzed. The proposed algorithm is applied to solve 13 test problems and its performance is compared with that of 10 widely used algorithms. The results show that the proposed algorithm can effectively handle nonconvex and complex problems, generate widely spread and uniformly distributed solutions on the entire Pareto front, and outperform those compared algorithms.

Research on multiobjective optimization problems becomes one of the hottest topics of intelligent computation. In order to improve the search efficiency of an evolutionary algorithm and maintain the diversity of solutions, in this paper, the learning automata (LA) is first used for quantization orthogonal crossover (QOX), and a new fitness function based on decomposition is proposed to achieve these two purposes. Based on these, an orthogonal evolutionary algorithm with LA for complex multiobjective optimization problems with continuous variables is proposed. The experimental results show that in continuous states, the proposed algorithm is able to achieve accurate Pareto-optimal sets and wide Pareto-optimal fronts efficiently. Moreover, the comparison with the several existing well-known algorithms: nondominated sorting genetic algorithm II, decomposition-based multiobjective evolutionary algorithm, decomposition-based multiobjective evolutionary algorithm with an ensemble of neighborhood sizes, multiobjective optimization by LA, and multiobjective immune algorithm with nondominated neighbor-based selection, on 15 multiobjective benchmark problems, shows that the proposed algorithm is able to find more accurate and evenly distributed Pareto-optimal fronts than the compared ones.

Instance coreference resolution is an essential problem in studying semantic web, and it is also critical for the implementation of web of data and future integration and application of semantic data. In this paper, we propose to use Memetic Algorithm (MA) to solve this instance coreference problem in a sequential stage, i.e., the instance-level matching is carried out with the result of schema-level matching. We first give the optimization model for schema-level matching and instance-level matching. Then, we, respectively, present profile similarity measures and the rough evaluation metrics with the assumption that the golden alignment for both schema-level matching and instance-level matching is one-to-one. Furthermore, we give the details of the MA. Finally, the experiments of comparing our approach with the state-of-the-art systems on OAEI benchmarks and real-world datasets are conducted and the results demonstrate that our approach is effective.

Among the many-objective optimization problems, there exists a kind of problem with redundant objectives, it is possible to design effective algorithms by removing the redundant objectives and keeping the non-redundant objectives so that the original problem becomes the one with much fewer objectives. In this paper, a new non-redundant objective set generation algorithm is proposed. To do so, first, a multi-objective evolutionary algorithm based decomposition is adopted to generate a small number of representative non-dominated solutions widely distributed on the Pareto front. Then, the conflicting objective pairs are identified through these non-dominated solutions, and the non-redundant objective set is determined by these pairs. Finally, the experiments are conducted on a set of benchmark test problems and the results indicate the effectiveness and efficiency of the proposed algorithm.

The era of big data computing is coming. As scientific applications become more data intensive, finding an efficient scheduling strategy for massive computing in parallel and distributed systems has drawn increasingly attention. Most existing studies considered single-installment scheduling models, but very few literature involved multi-installment scheduling, especially in heterogeneous parallel and distributed systems. In this paper, we proposed a new model for periodic multi-installment divisible-load scheduling in which the make-span of the workload is minimized, and a genetic algorithm was designed to solve this model. Finally, experimental results show the effectiveness and efficiency of the proposed algorithm.

Minimizing the make-span of the entire divisible load is the primary objective of multi-installment scheduling in heterogeneous parallel and distributed systems. This is a significantly difficult problem to address because we have to find the optimal number m of installments, optimal number n of processors taking part in computation, and optimal load partition A = [αij]n×mwith each element represents the load fraction assigned to each processor in different installment. Therefore, this problem involves 2+n m variables. In this paper, we first find the function expression of the optimal load partition A with respect to the number m of installments and the number n of processors participating in computation, i.e., A = f (n, m), thereby reducing the dimension of the problem down to 2. Then we propose a new heuristic method for finding the optimal numbers of installments and processors. Finally, experimental results show that the make span of the entire divisible load obtained by the proposed method is smaller than those by the existing multi-installment scheduling methods, which implies the effectiveness of the proposed method.

Clustering is a popular and effective method for image segmentation. However, existing cluster methods often suffer the following problems: (1) Need a huge space and a lot of computation when the input data are large. (2) Need to assign some parameters (e.g. number of clusters) in advance which will affect the clustering results greatly. To save the space and computation, reduce the sensitivity of the parameters, and improve the effectiveness and efficiency of the clustering algorithms, we construct a new clustering algorithm for image segmentation. The new algorithm consists of two phases: coarsening clustering and exact clustering. First, we use Affinity Propagation (AP) algorithm for coarsening. Specifically, in order to save the space and computational cost, we only compute the similarity between each point and its t nearest neighbors, and get a condensed similarity matrix (with only t columns, where t << N and N is the number of data points). Second, to further improve the efficiency and effectiveness of the proposed algorithm, the Self-tuning Spectral Clustering (SSC) is used to the resulted points (the representative points gotten in the first phase) to do the exact clustering. As a result, the proposed algorithm can quickly and precisely realize the clustering for texture image segmentation. The experimental results show that the proposed algorithm is more efficient than the compared algorithms FCM, K-means and SOM.

Evolutionary algorithms (EAs) are a kind of efficient and effective algorithms for global optimization problems. However, their efficiency and effectiveness will be greatly reduced for large scale problems. To handle this issue, a variable grouping strategy is first designed, in which the variables with the interaction each other are classified into one group, while the variables without interaction are classified into different groups. Then, evolution can be conducted in these groups separately. In this way, a large scale problem can be decomposed into several small scale problems and this makes the problem solving much easier. Furthermore, an auxiliary function, which can help algorithm to escape from the current local optimal solution and find a better one, is designed and integrated into EA. Based on these, a variable grouping based differential evolution algorithm (briefly, VGDE) using auxiliary function is proposed. At last, the simulations are made on the standard benchmark suite in CEC'2013, and VGDE is compared with several well performed algorithms. The results indicate the proposed algorithm VGDE is more efficient and effective.

For large scale global optimization problems, the efficiency and effectiveness of evolutionary algorithms (EAs) will be much reduced with the dimension increasing. In this paper, a novel evolutionary algorithm is proposed in order to improve the performance of EAs. In the proposed algorithm, on one hand, a variable grouping strategy is introduced. It can group all variables into several subcomponents, while the variables in each subcomponent are non-separable. In this way, a large scale problem can be decomposed into several small scale problems. On the other hand, a filled function with one parameter is integrated into EAs, which can help algorithm to escape from the current local optimal solution and find a better one. The simulations are made on the standard benchmark suite in CEC'2013, and the proposed algorithm is compared with several well performed algorithms. The results indicate the proposed algorithm is more efficient and effective.

Transforming a constrained optimization problem (COP) into a bi-objective optimization problem (BOP) is an efficient way to solve the COP. However, how to obtain a good balance between the objective function and the constraint violation function is not easy in BOP. To handle this issue, a novel unbiased bi-objective optimization model is proposed, in which both objective functions are equally treated. Furthermore, the novel model is shown to have the unique Pareto optimal vector under proper condition, and the Pareto optimal vector is exactly corresponding to the optimal solution of COP. Moreover, the relationship between the existing biased bi-objective model and the proposed unbiased one is analyzed in detail. For the unbiased model, a generic multi-objective optimization evolutionary algorithm, i.e. a differential evolution (DE), can be used to solve it, and Pareto ranking is employed as the unique selection criterion. The experiments are conducted on 24 well-known benchmark test instances and the results illustrate that the proposed model is not only effective but also efficient.

In the real world, many decision making problems often need to be modeled as a class of bilevel programming problems where fuzzy random coefficients are contained in both objective functions and constraint functions. To deal with these problems, an interval programming approach based on the α-level set is proposed to determine the optimal value range containing the best and worst optimal values so as to provide more information for decision makers. Furthermore, by incorporating expectation optimization model into probabilistic chance constraints, the best and worst optimal problems are transformed into deterministic ones. In addition, an estimation of distribution algorithm is designed to derive the best and worst Stackelberg solutions. Finally, a numerical example is given to show the application of the proposed models and algorithm.

In this paper, a novel evolutionary algorithm framework called smoothing and auxiliary functions based cooperative coevolution (Briefly, SACC) for large scale global optimization problems is proposed. In this new algorithm pattern, a smoothing function and an auxiliary function are well integrated with a cooperative coevolution algorithm. In this way, the performance of the cooperative coevolution algorithm may be improved. In SACC, the cooperative coevolution is responsible for the parallel searching in multiple areas simultaneously. Afterwards, an existing smoothing function is used to eliminate all the local optimal solutions no better than the best one obtained until now. Unfortunately, as the above takes place, the smoothing function will lose descent directions, which will weaken the local search. However, a proposed auxiliary function can overcome the drawback, which helps to find a better local optimal solution. A clever strategy on BFGS quasi-Newton method is designed to make the local search more efficient. The simulations on standard benchmark suite in CEC'2013 are made, and the results indicate the proposed algorithm SACC is effective and efficient.

The problem of divisible load scheduling in network based heterogeneous distributed systems is addressed in this paper, where a general platform is considered, and the communication is in non-blocking message receiving mode, moreover, the communication speeds, computation speeds, start-up overheads and workload size are arbitrary. To solve the problem efficiently, we set up an optimization model which can effectively tackle the following three issues: (1) how many and which processors are required in computation; (2) in which order the load fractions are distributed to processors; (3) how much the load fraction should be distributed to each processor. For this model, a novel genetic algorithm is proposed, and the convergence of the proposed algorithm to a globally optimal solution with probability one is proved. Finally, the experiments on several examples indicate the efficiency and effectiveness of the proposed algorithm.

Filters are important building blocks in signal processing circuits. Some researcher had successfully utilized genetic algorithm (GA) in design of filters. Nevertheless, filters obtained by GA are always complex and require lengthy computations. Ant colony optimization (ACO) is a novel searching technique used in optimization problems. In this paper, an ACO approach for optimization of analog filters is presented. In a design example, the order of a lowpass filter and the parameters of its components have been optimized in a discrete search space. AC analysis of the optimized filter has been conducted, and the results have been compared with a filter obtained by GA. The results show that filters obtained by ACO have simpler structures and better performance.

In the real world, many optimization problems are dynamic constrained multi-objective optimization problems. This requires an optimization algorithm not only to find the global optimal solutions under a specific environment but also to track the trajectory of the varying optima over dynamic environments. To address this requirement, a hyper rectangle search based particle swarm algorithm is proposed for such problems. This algorithm employs a hyper rectangle search to predict the optimal solutions (in variable space) of the next time step. Then, a PSO based crossover operator is used to deal with all kinds of constraints appearing in the problems when the time step (environment) is fixed. This algorithm is tested and compared with two well known algorithms on a set of benchmarks. The results show that the proposed algorithm can effectively track the varying Pareto fronts over time.

Soaring power consumption of data centers has drawn increasing attentions. Reducing energy consumption will not only cut down the operational cost of data centers, but also reduce the amount of greenhouse gases emissions. From the perspective of optimizing energy efficiency of servers in a data center, and by taking data layout policies and the requirement of data locality for task execution, as well as the relationship between servers' performance and energy consumption into consideration, a new bi-level multiobjective task scheduling model based on MapReduce is proposed first. To sole the problem efficiently, a tailor-made encoding and decoding methods are designed, then, two explicit objective functions, energy efficiency function and localized ratio function are defined. Based on all these, an improved bi-level multiobjective evolutionary algorithm based on MOEA/D is proposed to solve this model, in which a local search operator is introduced to accelerate its convergent speed and enhance its searching ability. Finally, simulation results show that the proposed algorithm is effective and efficient.

This work deals with a class of nonlinear bilevel programming problems with nonconvex objective functions, in which the follower objective is a function of linear expression of all variables and the follower constraints are linear. For the leader functions, there are no any restrictions on the convexity as well as the differentiability. The distinguished feature of the problem is the nonconvexity of the follower objective function, which breaks through the barrier that the follower must be convex or concave in literature. First, for any fixed leader variable x, two linear programming are got from the follower and used to obtain the follower optimal solution y. In addition, in order to avoid solving directly the follower problem for each x, a real-binary encoding scheme is given which consists of x and the bases of two linear programming. Finally, a new crossover operator is designed based on the characteristics of the mixed encoding, and a novel genetic algorithm is proposed. The numerical results on 15 examples illustrate that the proposed algorithm is effective and stable.

When the leader's objective function of a nonlinear bilevel programming problem is nondifferentiable and the follower's problem of it is nonconvex, the existing algorithms cannot solve the problem. In this paper, a new effective evolutionary algorithm is proposed for this class of nonlinear bilevel programming problems. First, based on the leader's objective function, a new fitness function is proposed that can be easily used to evaluate the quality of different types of potential solutions. Then, based on Latin squares, an efficient crossover operator is constructed that has the ability of local search. Furthermore, a new mutation operator is designed by using some good search directions so that the offspring can approach a global optimal solution quickly. To solve the follower's problem efficiently, we apply some efficient deterministic optimization algorithms in the MATLAB Toolbox to search for its solutions. The asymptotically global convergence of the algorithm is proved. Numerical experiments on 25 test problems show that the proposed algorithm has a better performance than the compared algorithms on most of the test problems and is effective and efficient.

There are many global optimization problems arisen in various fields of applications. It is very important to design effective algorithms for these problems. However, one of the key drawbacks of the existing global optimization methods is that they are not easy to escape from the local optimal solutions and can not find the global optimal solution quickly. In order to escape from the local optimal solutions and find the global optimal solution fast, first, a smoothing function, which can flatten the landscape of the original function and eliminate all local optimal solutions which are no better than the best one found so far, is proposed. This can make the search of the global optimal solution much easier. Second, to cooperate the smoothing function, a tailor-made search scheme called circle search is presented, which can quickly jump out the flattened landscape and fall in a lower landscape quickly. Third, a better solution than the best one found so far can be found by local search. Fourth, a crossover operator is designed based on uniform design. Based on these, a smoothing evolutionary algorithm for global optimization is proposed. At last, the numerical simulations for eight high dimensional and very challenging standard benchmark problems are made. The performance of the proposed algorithm is compared with that of nine evolutionary algorithms published recently. The results indicate that the proposed algorithm is statistically sound and has better performance for these test functions.

In this paper, we propose a uniform enhancement approach called smoothing function method, which can cooperate any optimization algorithm and improve its performance. The method has two phases. In the first phase, a smoothing function is constructed by using a properly truncated Fourier series. It can preserve the overall shape of the original objective function but eliminate many of its local optimal points, thus it can well approach the objective function. Then, the optimal solution of the smoothing function is searched by an optimization algorithm (e.g. traditional algorithm or evolutionary algorithm) so that the search becomes much easier. In the second phase, we switch to optimize the original function for some iterations by using the best solution(s) obtained in phase 1 as an initial point (population). Thereafter, the smoothing function is updated in order to approximate the original function more accurately. These two phases are repeated until the best solutions obtained in several successively second phases cannot be improved obviously. In this manner, any optimization algorithm will become much easier in searching optimal solution. Finally, we use the proposed approach to enhance two typical optimization algorithms: Powell direct algorithm and a simple genetic algorithm. The simulation results on ten challenging benchmarks indicate the proposed approach can effectively improve the performance of these two algorithms.

In this paper, an infeasible elitist based particle swarm optimization is proposed for solving constrained optimization problems. Firstly, an infeasible elitist preservation strategy is proposed, which keeps some infeasible solutions with smaller rank values at the early stage of evolution regardless of how large the constraint violations are, and keep some infeasible solutions with smaller constraint violations and rank values at the later stage of evolution. In this manner, the true Pareto front will be found easier. Secondly, in order to find a set of diversity and uniformly distributed Pareto optimal solutions, a new crowding distance function is designed. It can assign large function values not only for the particles located in the sparse regions of the objective space but also for the crowded particles located near to the boundary of the Pareto front as well. Thirdly, a new mutation operator with two phases is proposed. In the first phase, the particles whose constraint violations are less than the threshold value will be used to compute the total force, then the force will be used as a mutation direction, being helpful to find the better solutions along this direction. In order to guarantee the convergence of the algorithm, the second phase of mutation is proposed. Finally, the convergence of the algorithm is proved. The comparative study shows that the proposed algorithm can generate widespread and uniformly distributed Pareto fronts and outperforms those compared algorithms.

Designing efficient algorithms for difficult multi-objective optimization problems is a very challenging problem. In this paper a new clustering multi-objective evolutionary algorithm based on orthogonal and uniform design is proposed. First, the orthogonal design is used to generate initial population of points that are scattered uniformly over the feasible solution space, so that the algorithm can evenly scan the feasible solution space once to locate good points for further exploration in subsequent iterations. Second, to explore the search space efficiently and get uniformly distributed and widely spread solutions in objective space, a new crossover operator is designed. Its exploration focus is mainly put on the sparse part and the boundary part of the obtained non-dominated solutions in objective space. Third, to get desired number of well distributed solutions in objective space, a new clustering method is proposed to select the non-dominated solutions. Finally, experiments on thirteen very difficult benchmark problems were made, and the results indicate the proposed algorithm is efficient.

The existing shelf space allocation methods only optimize the profits without considering the sales time. Actually, the time to sale the products is important as well to retailers because the time has a significant impact on the liquidity and long-term profits of a retail shop. Hence, this paper proposes a bi-objective model, in which one objective is to maximize the total profits of all store's products whereas the other objective is to minimize the total time to sale the store's products. By transforming this model into a single objective problem, we optimize the shelf space allocation problem in terms of the retail profits and sales time using a hybrid genetic algorithm (GA), in which three improved local search methods are designed to improve the GA performance on local search. Further, the new multi-criteria selection scheme is also designed to maintain diversity of population. The experimental results show that the proposed model outperforms the existing method in terms of profit per unit time.

In this paper, the level-set evolution is exploited in the design of a novel evolutionary algorithm (EA) for global optimization. An application of Latin squares leads to a new and effective crossover operator. This crossover operator can generate a set of uniformly scattered offspring around their parents, has the ability to search locally, and can explore the search space efficiently. To compute a globally optimal solution, the level set of the objective function is successively evolved by crossover and mutation operators so that it gradually approaches the globally optimal solution set. As a result, the level set can be efficiently improved. Based on these skills, a new EA is developed to solve a global optimization problem by successively evolving the level set of the objective function such that it becomes smaller and smaller until all of its points are optimal solutions. Furthermore, we can prove that the proposed algorithm converges to a global optimizer with probability one. Numerical simulations are conducted for 20 standard test functions. The performance of the proposed algorithm is compared with that of eight EAs that have been published recently and the Monte Carlo implementation of the mean-value-level-set method. The results indicate that the proposed algorithm is effective and efficient.

In this paper, a special nonlinear bilevel programming problem (nonlinear BLPP) is transformed into an equivalent single objective nonlinear programming problem. To solve the equivalent problem effectively, we first construct a specific optimization problem with two objectives. By solving the specific problem, we can decrease the leader's objective value, identify the quality of any feasible solution from infeasible solutions and the quality of two feasible solutions for the equivalent single objective optimization problem, force the infeasible solutions moving toward the feasible region, and improve the feasible solutions gradually. We then propose a new constraint-handling scheme and a specific-design crossover operator. The new constraint-handling scheme can make the individuals satisfy all linear constraints exactly and the nonlinear constraints approximately. The crossover operator can generate high quality potential offspring. Based on the constraint-handling scheme and the crossover operator, we propose a new evolutionary algorithm and prove its global convergence. A distinguishing feature of the algorithm is that it can be used to handle nonlinear BLPPs with nondifferentiable leader's objective functions. Finally, simulations on 31 benchmark problems, 12 of which have nondifferentiable leader's objective functions, are made and the results demonstrate the effectiveness of the proposed algorithm.