Evolutionary algorithms have been used to solve various optimization problems by iteratively refining solutions through the process inspired by natural evolution. To reduce the randomness inherent, multiple trials are often performed on a single problem, producing a wealth of data that may hold valuable optimization insights. However, traditional EAs usually discard this accumulated experience when tackling new optimization tasks. To address this issue, a novel evolutionary computation paradigm, i.e., learning-aided evolutionary optimization, was developed to exploit past optimization knowledge to enhance search efficiency. In this regard, we propose an offline knowledge learning (OKL) framework, consisting of two key phases: (1) extracting knowledge from past successful optimization runs and (2) applying the knowledge to guide the evolutionary search process. Specifically, we employ a neural network as the knowledge model to generate promising offspring during the optimization process. Additionally, an adaptive mechanism is introduced to dynamically control the rate at which the knowledge model is utilized. Experiments are conducted using genetic algorithm (GA) as the backbone optimizer, resulting in the OKL-GA approach. The results demonstrate that the OKL framework can effectively leverage previous optimization knowledge, enabling generation of fitter offspring and significantly improving performance.

Robust optimization over time (ROOT) aims to find robust solutions that can withstand environmental changes rather than merely identifying the global optima. The primary goal of ROOT is to seek a solution whose quality remains acceptable over an extended period of time. Existing methods mostly rely on historical data to predict solution robustness and extract characteristic information from the environment. In light of the advantages of reinforcement learning in adaptability and learning, this study proposes a new method, called fluctuation and robustness based reinforcement learning in particle swarm optimization (RB-PSO), to address the problem. By collecting the information about fitness variation of solutions evaluated under identical decision variables across different environmental conditions, the reinforcement learning framework in RB-PSO leverages the data to enhance the performance of PSO in robustness and adaptability. Experimental results demonstrate that the proposed RB-PSO consistently outperforms PSO in terms of both survival time and solution quality, particularly under varying levels of environmental dynamics and across multiple dimensions. Moreover, RB-PSO exhibits superior stability and adaptability compared to RL-PSO, achieving competitive or better performance in survival time and solution quality, making it a highly promising approach for addressing ROOT problems.

Natural language processing (NLP) research has achieved remarkable advancement in recent decades. Language data and music data share several common features, enabling NLP techniques to be applied to music-related tasks, including music generation. One of the fundamental techniques in NLP is tokenization, which is designed to create more efficient representations of text. Inspired by the shared nature of language and music, this study proposes using tokenization algorithms to design a high-level representation that facilitates evolutionary music composition. Traditional evolutionary music composition systems typically employ an integer string to represent a melody. In contrast, the tokenized representation can encode more complex melodic information with a shorter chromosome than integer strings. A series of experiments were conducted to evaluate the effectiveness and efficiency of the proposed representation. The results demonstrate a significant improvement in both the expressiveness and efficiency of melody composition.

Multimodal multiobjective optimization problems (MMOPs) present a specific category of multiobjective problems. Unlike conventional multiobjective problems where Pareto opti-mal solutions gather in one or few regions in the decision space, MMOPs aim to find solutions spread across various regions. In particular, these solutions may share similar locations in objective space, making the problem more complex and challenging. Most multiobjective optimization evolutionary algorithms (MOEAs) barely preserve diversity in decision space, whereas multimodal multiobjective optimization evolutionary algorithms (MMOEAs) require additional techniques such as clustering to maintain diversity in the decision space. In this study, we propose a new method that enables two sub populations and a clustering technique for diversity preservation. Furthermore, different clustering methods are compared to investigate their impact on performance. The experimental results show that the proposed method achieves better inverted generational distance in decision space (IGDX), indicating the effectiveness of the diversity preservation approach. In addition, the varying IGDX and inverted generational distance (IGD) obtained from different clustering methods reveal their different strengths in solving MMOPs.

The constrained multiobjective optimization problem (CMOP) is common in the real-world applications that need to simultaneously optimize conflicting objectives under certain constraints. In the past two decades, considerable efforts have been devoted to designing constrained multiobjective evolutionary algorithms (CMOEAs) for solving the CMOP. However, as the constraints become more complex, CMOEAs encounter a significant challenge of finding a set of well-distributed Pareto optimal solutions. The infeasible regions caused by the constraints become a major challenge in solving the CMOP since they hinder the population from moving toward the constrained Pareto front. The landscape of infeasible regions plays a significant role in the CMOP but is not well-studied. The present study aims to explore the influences of different landscapes of infeasible regions on the difficulty in solving a CMOP. To this end, we propose an approach to adjusting the landscapes through weights and present the MOEA/D-WSCV that enables the adjustment accordingly. The experimental results show that the inverted generation distance (IGD) and hypervolume (HV) obtained from MOEA/D-WSCV vary with weights, indicating the influences of infeasible regions upon the difficulty in solving CMOPs.

Floorplanning is a crucial process in the early stage of VLSI physical design. It determines the performance, reliability, and size of chips. B*-tree is a simple yet efficient representation that encodes the layout of modules in a compact and non-slicing structure. Several B*-tree variants and corresponding operators have been proposed to deal with non-slicing floorplanning. However, these operators are considered and applied individually. A collective manipulation of them remains missing. This study proposes a genetic algorithm (GA) that enables multiple crossover and mutation operators for solving the non-slicing floorplanning problem. In particular, the GA selects one crossover operator and one mutation operator from the pool of operators whenever reproducing an offspring. The probability for an operator to be selected is based on its empirical performance. This study conducts experiments on two well-known benchmarks to examine the effectiveness of the proposed method. The experimental results show that the GA can achieve superior solution quality and efficiency on the non-slicing VLSI floorplanning.

Origami is a folding technique that can be used to create paper models. This technique has diverse applications in art, engineering, and medical devices, such as tessellations, deployable structures, and venous stents. Recently, a number of approaches have been developed to generate crease patterns for desired paper models. Most of the existing methods are specially designed to handle one or a few certain types of topologies and thus have limited applicability. To address this issue, this study proposes a genetic algorithm (GA) to generate crease patterns for orthogonal-structure origami models. Two crease pattern representations, i.e., string and matrix, are designed for the GA to deal with crease pattern search. The experimental results on three test instances indicate that the GA is capable of finding the target crease patterns. In particular, the string representation leads to faster convergence than the matrix representation. These outcomes show the potential of GA for origami design.

Convolutional neural networks (CNNs) have achieved state-of-the-art performance in many image classification tasks. However, training a deep CNN requires a massive amount of training data, which can be expensive or unobtainable in practical applications, such as defect inspection and medical diagnosis. Transfer learning has been developed to address this issue by transferring knowledge learned from source domains to target domains. A common approach is fine-tuning, which adapts the parameters of a trained neural network for the new target task. Nevertheless, the network architecture remains designed for the source task rather than the target task. To optimize the network architecture in transfer learning, we propose a two-stage evolutionary neural architecture search for transfer learning (EvoNAS-TL), which searches for an efficient subnetwork of the source model for the target task. EvoNAS-TL features two search stages: 1) structure search and 2) local enhancement. The former conducts a coarse-grained global search for suitable neural architectures, while the latter acts as a fine-grained local search to refine the models obtained. In this study, neural architecture search (NAS) is formulated as a multiobjective optimization problem that concurrently minimizes the prediction error and model size. The knee-guided multiobjective evolutionary algorithm, a modern multiobjective optimization approach, is employed to solve the NAS problem. In this study, several experiments are conducted to examine the effectiveness of EvoNAS-TL. The results show that applying EvoNAS-TL on VGG-16 can reduce the model size by 52%–85% and simultaneously improve the testing accuracy by 0.7%–6.9% in transferring from ImageNet to CIFAR-10 and NEU surface detection datasets. In addition, EvoNAS-TL performs comparably to or better than state-of-the-art methods on the CIFAR-10, NEU, and Office-31 datasets.

Development of artificial intelligence has enabled automation of diverse complicated tasks, such as planning, scheduling, and natural language processing. As one of the complicated tasks, music composition involves various aspects, e.g., melody, rhythm, harmonization, phrasing, and forms. Evolutionary composition systems ordinarily formulate music composition as an optimization problem and adopt evolutionary algorithms to deal with it. This study focuses on evolutionary composition on a special genre-Bossa Nova. The proposed system uses integer-coded genetic algorithm to generate the melody, followed by a postprocess for arranging suitable accompaniment. In particular, the genetic algorithm features evaluation rules derived from music theory for consonant melodies. The postprocess creates a treble part and a bass part which together form the chord accompaniment on the basis of Bossa Nova harmony and rhythmic patterns. This study conducts experiments for quality verification of the generated music. Experimental results show that the proposed rules are able to guide genetic algorithm for composing harmonious melodies, and the accompaniments from postprocess blend well with the generated melodies. By and large, the integration of generated melodies and accompaniments presents satisfactory Bossa Nova music.

Evolutionary multitasking is a significant emerging search paradigm that utilizes evolutionary algorithms to concurrently optimize multiple tasks. The multi-factorial evolutionary algorithm renders an effectual realization of evolutionary multitasking on two or three tasks. However, there remains room for improvement on the performance and capability of evolutionary multitasking. Beyond three tasks, this paper proposes a novel framework, called the symbiosis in biocoenosis optimization (SBO), to address evolutionary many-tasking optimization. The SBO leverages the notion of symbiosis in biocoenosis for transferring information and knowledge among different tasks through three major components: 1) transferring information through inter-task individual replacement, 2) measuring symbiosis through intertask paired evaluations, and 3) coordinating the frequency and quantity of transfer based on symbiosis in biocoenosis. The inter-task individual replacement with paired evaluations caters for estimation of symbiosis, while the symbiosis in biocoenosis provides a good estimator of transfer. This study examines the effectiveness and efficiency of the SBO on a suite of many-tasking benchmark problems, designed to deal with 30 tasks simultaneously. The experimental results show that SBO leads to better solutions and faster convergence than the state-of-the-art evolutionary multitasking algorithms. Moreover, the results indicate that SBO is highly capable of identifying the similarity between problems and transferring information appropriately.

The k-nearest neighbors algorithm (kNN) is renowned for solving classification tasks. The notion of kNN is to seek similar data instances in the dataset as prediction reference, for which the similarity between instances is ordinarily measured by Euclidean distance. Recently, some studies propose problem-tailored distance metrics to improve the classification performance of kNN. In this paper, we utilize genetic programming to learn the transformation function, which interprets the relationship of two data instances into a scalar differential. The differential of data pairs indicates the dissimilarity between two instances. This study considers two forms of transformation functions. Experimental results show the transform functions learned by GP can effectively enhance the performance of kNN.

Classification is a significant task in machine learning. Common classification algorithms include decision tree, k-nearest neighbors (kNN), support vector machine, and so on. The kNN algorithm is a simple yet useful classification tool in practice. However, its performance may be deeply affected by the properties of dataset, such as imbalance of classes and noisy features. To deal with these problems and enhance the performance of classification, this study proposes optimizing the distance function and class-voting weights of kNN by genetic algorithm. The proposed method is called evolutionary optimized feature and class weights kNN (FCWkNN). The performance of FCWkNN is examined on different datasets. Experimental results show that the combined optimization of feature weights and class weights is capable of improving kNN on imbalanced datasets.

Evolutionary algorithms (EAs) have shown their great capability of handling optimization problems. In the domain of large scale global optimization, many distributed EAs (dEAs) have been proposed for maintaining population diversity so as to enhance their efficacy. One well-known variant of dEA is the island model EA, in which several populations form islands communicating through migration. There are several key factors that affect the performance and search behavior of island model EA, such as population size of each island and migration topology. While most studies of dEA focus on low or medium dimensional problems, an investigation into the effects of these factors on high dimensional problems is greatly needed. This study presents an empirical analysis of island model EA on large scale global optimization problems. The analysis examines the solution quality, convergence speed, and population diversity of island model EA with different migration topologies, population sizes, migration rates, and migration frequencies on four benchmark function of 1,000 dimensions. The results render guidelines for using island model EA to solve large scale global optimization problems.

Many real-world problems encounter varying environments while searching for the optimal solutions. Problems of these kinds are known as dynamic optimization problems. Evolutionary algorithms (EAs) have shown their high capability of solving dynamic optimization problems. The large number of fitness evaluations, however, limits the utility of EAs in dynamic optimization with expensive fitness evaluation. This study proposes a fitness inheritance method based on k-nearest neighbors (kNN) to reduce the number of fitness evaluations. This fitness inheritance method is applied to the covariance matrix adaptation evolution strategy (CMAES), a state-of-the-art evolutionary algorithm for complex numerical optimization problems, to save fitness evaluations and improve search efficiency. This study further presents a convergence checking operator to maintain a reasonable accuracy of fitness inheritance by reinitializing the population and multivariate normal distribution model timely. Experimental results verify the effectiveness and efficiency of the proposed method on six benchmark problems of dynamic optimization.

Multi-objective optimization is a significant topic since many real-world problems consider different aspects. The potential conflicts among the aspects make optimization even more difficult. The MOEA/D-CMAES has shown its capability in tackling complex multi-objective optimization problems. However, MOEA/D-CMAES needs to limit the offspring population size of each subproblem to save computational cost, which causes its vulnerability to premature convergence due to the deficiency of sampling points. This study aims to address this issue with two features: fitness inheritance and information sharing. More specifically, fitness inheritance is used to reduce the computational cost at fitness evaluation and therefore enables a larger size of offspring population. In addition, information sharing facilitates communication and utilization of offspring information among different subproblems. A series of experiments are conducted on the complex multi-objective problems. The experimental results show that the proposed MOEA/D-FICMAES is effective and efficient in solving the complex multi-objective optimization problems, in comparison to two decomposition based and one fitness inheritance assisted multiobjective optimization evolutionary algorithms.

The Set -Cover problem aims to partition a set of nodes for the maximal number of covers. This problem is crucial for extending the lifetime of wireless sensor networks (WSNs) under the constraint of covering all targets. More specifically, the Set -Cover problem enables partitioning the set of sensors into several covers over all targets and activating the covers by turns to effectively extend the WSN lifetime. To resolve this problem, we propose a novel memetic algorithm (MA) based on integer-coded genetic algorithm and local search. This paper adapts the crossover and mutation operators to integer representation and, furthermore, designs a new fitness function that considers both the number of covers and the contribution of each sensor to covers. A local improvement method, called the recycling operator, is developed to enhance the performance on the Set -Cover problem. Experimental results show that the proposed MA significantly outperforms five evolutionary algorithms in terms of the number of covers obtained, hit rate (HR), and running time. In particular, the new MA increases 38.1% HR and saves 78.7% running time of state-of-the-art MA on average. The preferable results validate the effectiveness and efficiency of the proposed MA for the Set -Cover problem.

Evolutionary multitasking is an emergent topic in evolutionary computation area. Recently, a well-known evolutionary multitasking method, the multi-factorial evolutionary algorithm (MFEA), has been proposed and applied to concurrently solve two or three problems. In MFEA, individuals of different tasks are recombined in a predefined random mating probability. As the number of tasks increases, such recombination of different tasks becomes very frequent, thereby detracting the search from any specific problems and limiting the MFEA's capability to solve many-tasking problems. This study proposes a general framework, called the evolution of biocoenosis through symbiosis (EBS), for evolutionary algorithms to deal with the many-tasking problems. The EBS has two main features: the selection of candidates from concatenate offspring and the adaptive control of information exchange among tasks. The concatenate offspring represent a set of offspring used for all tasks. Moreover, this study presents a test suite of many-tasking problems (MaTPs), modified from the CEC 2014 benchmark problems. The Spearman correlation is adopted to analyze the effect of the shifts of optima on the MaTPs. Experimental results show that the effectiveness of EBS is superior to that of single task optimization and MFEA on the four MaTPs. The results also validate that EBS is capable of exploiting the synergy of fitness landscapes.

Evolutionary composition has received considerable attention in these years. An automatic composition system based on evolutionary computation is attractive but very challenging because the evaluation function is difficult to design: First, human's evaluation on a composition is subject to personal feeling and preference. Second, different regions form their unique music genres from local customs, lifestyle, or ethnic history. These genres enrich music diversity and human sensation. This study presents an evolutionary composition system to address the above two issues. More specifically, the proposed system adopts general music theory rules as the fundamentals of fitness evaluation, thereby ensuring the basic harmony and consonance. In addition, we explore the specific musical expressions of Flamenco and Argentine Tango, and include their features in the evolutionary composition system to create a fusion. Experimental results show that the generated music is satisfactory and can express the emphases of both Flamenco and Argentine Tango.

Evolutionary multitasking aims to explore implicit synergy among multiple optimization tasks. Through the effect of hitchhiking, evolutionary multitasking is capable of improving the performance of evolutionary algorithms on exploration as well as exploitation. Multifactorial evolutionary algorithm (MFEA) presented an effectual implementation of evolutionary multitasking, which simultaneously seeks the solutions to multiple optimization problems by unifying their search spaces. The MFEA enables information sharing across tasks during evolution. This mechanism can improve the evolutionary efficiency in the early phase; however, it will impair the exploitation and consume extra resources later on, due to the essential difference among the fitness landscapes of optimization problems. This study proposes detecting the occurrence of parting ways, at which the information sharing begins to fail. In addition, we develop the resource allocation mechanism to reallocate the fitness evaluations on different types of offspring by ceasing information sharing when parting ways. Experiments are conducted to evaluate the proposed methods. The experimental results show that applying parting ways detection and resource reallocation for MFEA can achieve better solution quality in most of testing cases, especially when the tasks share low similarity of landscapes.

Evolution strategy (ES) has shown to be effective in many search and optimization problems. In particular, the ES with covariance matrix adaptation (CMAES) achieves great successes and is viewed as a state-of-the-art evolutionary algorithm for complex numerical optimization. The CMAES models the population by a multivariate normal distribution, which requires a considerable amount of fitness evaluation results and thus degrades its efficiency. This paper proposes using fitness inheritance to reduce the computational cost at fitness evaluation. More specifically, the proposed FI-CMAES adopts fitness inheritance to approximate the fitness of offspring. The survivors are selected according to the approximated fitness; thereafter, the survival offspring are evaluated by the original fitness function. By this way, several original fitness evaluations on offspring can be saved. Experiments examine the effectiveness and efficiency of FI-CMAES on the CEC2014 test suite. The results show that FI-CMAES can outperform CMAES in terms of solution quality and convergence speed.

Multi-objective optimization is a blooming research area since many real-world problems comprise multiple objectives. Multi-objective evolutionary algorithms (MOEAs) have been widely used to solve the multi-objective optimization problems. In particular, the decomposition based MOEA (MOEA/D) has achieved considerable successes in tackling multi-objective optimization problems. The covariance matrix adaptation evolution strategy (CMAES) is known for its effectiveness in solving complex numerical optimization problems. This study integrates CMAES into MOEA/D as the MOEA/D-CMAES for the merits of MOEA/D framework in multi-objective optimization and CMAES in complex numerical optimization. In MOEA/D-CMAES, each subproblem is handled with one CMAES. To avoid the drastic increase in the number of offspring generated and their fitness evaluations, MOEA/D-CMAES generates only one offspring in each subproblem. The multivariate normal distribution in each CMAES is updated by the collaboration of the offspring generated in the present subproblem and those of other subproblems. Experimental results show that MOEA/D-CMAES outperforms MOEA/D using differential evolution in terms of hypervolume and convergence speed, which validate the effectiveness and efficiency of MOEA/D-CMAES in multi-objective optimization.

Genetic programming (GP) has received considerable successes in machine learning tasks such as prediction and classification. Ensemble learning enables the collaboration of multiple classifiers and effectively improves the classification accuracy. Learning an ensemble of classifiers with GP can simply be achieved by repeated runs of GP; however, the computational cost will be multiplied as well. Recently, multifactorial evolution was proposed to concurrently solve multiple problems with a single population. This study utilizes the multifactorial evolution and designs a multifactorial genetic programming (MFGP) for efficiently learning an ensemble of decision trees. In the MFGP, each task is associated with one run of GP. The multifactorial evolution enables MFGP to evolve multiple GP classifiers for an ensemble in a single run, which saves a substantial amount of computational cost at repeated runs of GP. The experimental results show that MFGP can learn an ensemble with comparable accuracy, precision, and recall to conventional ensemble learning methods, whereas MFGP requires much less computational resource. The satisfactory outcomes validate the advantages of MFGP in ensemble learning.

Artificial intelligence (AI) has bloomed in many novel fields such as computational creativity. Recently, research on automatic composition using AI technology, especially evolutionary algorithms, has received considerable promising results. Traditionally, chromosomes are represented as a series of numbers to indicate the notes for evolutionary composition. This study attempts to explore the composition styles by mining music patterns of a specific composer. The patterns are used as genes for chromosome representation. Accordingly, the composition styles are considered in generating music by evolutionary algorithms. The fitness function is based on music theory to smooth the progression between phrases. Experimental results show that the patterns mined from compositions can reflect the composer's style and benefit generating satisfactory songs by evolutionary algorithms.

The pickup and delivery problem combines vehicle routing and objects distribution to cope with logistic problems. While most research on PDP aims to minimize the transportation cost for the sake of service providers, this study proposes the minimum latency pickup and delivery problem (MLPDP) that seeks a low-latency route to transport commodities among nodes, where latency represents the sum of transportation time between demanders and the corresponding suppliers. The MLPDP is pertinent to time-sensitive services and logistics focusing on customer satisfaction. This study defines the latency of a customer as the average time elapsed aboard of goods received. The last-in-first-out loading method is employed to simulate real-world rear-loaded vehicles. This study further designs a genetic algorithm (GA) to resolve the MLPDP. In particular, we propose the edge aggregate crossover (EAC) and the reversely weighting technique to improve the performance of GA on the MLPDP. Experimental results show the effectiveness of the proposed GA. The results further indicate that EAC leads to significantly better performance than conventional crossover operators in solution quality and convergence speed on the MLPDP.

Composing music through evolutionary algorithms has received increasing attention recently. To establish a standard of composing, some studies were proposed on the basis of analysis on musicians, statistics of music details, and rule of thumbs. These methods have achieved some promising results; however, generating melody is still a formidable challenge to computer composition because of the considerable permutations of notes. This study develops a genetic algorithm (GA) based on music theory to generate melody. In particular, we use the rhythm of existing songs as the basis to generate new compositions instead of generating music from scratch; that is, the GA keeps the rhythm of an existing song and rearranges the pitches of all notes for a new composition. Three crossover operators are further proposed to improve the performance of GA on composition. The experimental results show that the GA can achieve satisfactory compositions. The three crossover operators outperform 2-point crossover in the fitness of resultant compositions.

Lifetime is a critical issue at wireless sensor networks (WSNs). Partitioning the set of sensors into several covers over all targets and enabling the covers by turns can effectively extend the lifetime. The problem formulation regarding optimization of sensor partition commonly assumes static networks; however, the composition and topology of real-world WSNs can vary with time due to hardware failure or communication error. This study considers extending the lifetime of dynamic WSNs; specifically, some sensors may fail or recover during the lifetime. In addition, we propose two genetic algorithms (GAs) to deal with this dynamic optimization problem. A series of simulations was conducted to examine the performance of the proposed algorithms. The simulation results validate the effectiveness of the GAs on extending the lifetime under dynamic network environment.

The selective pickup and delivery problem (SPDP) is a novel variant of the pickup and delivery problem. This problem relaxes the constraint that all pickup nodes must be visited along the route. Specifically, the SPDP aims to find the shortest route that can supply delivery nodes with required commodities from some selected pickup nodes. Selection of pickup nodes is capable of reducing the transportation cost; on the other hand, it increases the search space and difficulty in resolving the SPDP. In this study, we propose an adaptive mutation that focuses on the selection of proper pickup nodes for the SPDP. Two evolutionary algorithms (EAs), namely genetic algorithm and memetic algorithm, for the SPDP are developed as well. Experimental results show that the proposed adaptive mutation can lead to better selection of pickup nodes for shorter routes, which validates its effectiveness on improving the two EAs for the SPDP.

Computational creativity using artificial intelligence and computational intelligence has received increasing attention. Automatic music composition is a blooming field in computational creativity; especially, automatic accompaniment has gained some promising results. However, most of the automatic accompaniment systems based on evolutionary computation require human feedback as evaluation criterion, which is vulnerable to the fatigue and decreased sensitivity after long-time listening. This study adopts music theory as the basis of evaluation criterion for accompaniment to address this issue. Specifically, we develop a genetic algorithm (GA) to generate polyphonic accompaniment, in which the fitness function consists of several evaluation rules based on music theory. Three accompaniments, i.e., main, bass, and chord accompaniments are considered in the study. Experimental results show that, given a dominant melody, the proposed method can effectively generate multiple scores to form polyphonic accompaniment.

In LTE-Advanced or 802.16m WiMAX-based relay networks, the downlink broadcast of massive amounts of data is a crucial application. To help the application save the radio resource consumption significantly, it is necessary to find the minimum resource allocation such that the Base Station (BS) and all designated Mobile Stations (MSs) are connected via a subset of Relay Stations (RSs). In this context, the allocation problem can be seen as a path construction problem. In this paper, we formulate the path construction problem as an integer linear programming (ILP) model. Because of the computational complexity of ILP, we propose an algorithm, called the Resource Diminishing Principle (RDP), to address the problem. We evaluate the performance of RDP by a series of simulations. The simulation results show that RDP meets the desired targets, and also outperforms existing solutions.

The multi-vehicle selective pickup and delivery problem (MVSPDP) is a class of vehicle routing problem. The MVSPDP aims to minimize the total distance traveled by a fleet of vehicles to collect and supply commodities, subject to vehicle capacity and travel distance. This problem relaxes the constraint that the vehicles have to visit all customers. In the MVSPDP, vehicles only need to collect sufficient commodities from some selected pickup nodes for all delivery nodes. To resolve the problem, this study develops a genetic algorithm with path relinking (GAPR). A repair operator is presented for the GAPR to handle the constraints. Experimental results on fourteen benchmarks validate the effectiveness of the proposed GAPR for the MVSPDP.

In the past, we proposed a GA-based clustering method for attribute clustering and feature selection. The fitness of each individual was evaluated using both the average accuracy of attribute substitutions in clusters and the cluster balance. The evaluation was, however, quite time-consuming. In this paper, we modify the previous method for a better execution performance based on feature similarity and feature dependence. The fitness of a chromosome combines both the total degrees of similarity between pairs of features and the accuracy of centers rather than the average accuracy by all the combinations. Experimental results also show the performance of the proposed approach.

The pickup and delivery problem addresses the real-world issues in logistic industry and establishes an important category of vehicle routing problems. The problem is to find the shortest route to collect and distribute objects under the assumption that the total supply and the total demand are in equilibrium. This study formulates a new problem, called the selective pickup and delivery problem (SPDP), by relaxing the constraint that all pickup nodes must be visited. Specifically, the SPDP aims to find the shortest route that can supply delivery nodes with required commodities from some pickup nodes. This problem can substantially reduce the transportation cost and fits some real-world scenarios. Furthermore, this study proposes a genetic algorithm (GA) to resolve the SPDP. A repair strategy is designed for the GA to deal with the constraint in the SPDP. Experimental results validate the effectiveness of the proposed GA in selecting pickup nodes and arranging the route. Moreover, the results demonstrate the characteristics and utility of the SPDP.

MOTIVATION: Integrated analysis of single nucleotide polymorphisms (SNPs) and structure variations showed that the extent of linkage disequilibrium is common across different types of genetic variants. A subset of SNPs (called tag SNPs) is sufficient for capturing alleles of bi-allelic and even multi-allelic variants. However, accuracy and power of tag SNPs are affected by several factors, including genotyping failure, errors and tagging bias of certain alleles. In addition, different sets of tag SNPs should be selected for fulfilling requirements of various genotyping platforms and projects. RESULTS: This study formulates the problem of selecting tag SNPs into a four-objective optimization problem that minimizes the total amount of tag SNPs, maximizes tolerance for missing data, enlarges and balances detection power of each allele class. To resolve this problem, we propose evolutionary algorithms incorporated with greedy initialization to find non-dominated solutions considering all objectives simultaneously. This method provides users with great flexibility to extract different sets of tag SNPs for different platforms and scenarios (e.g. up to 100 tags and 10% missing rate). Compared to conventional methods, our method explores larger search space and requires shorter convergence time. Experimental results revealed strong and weak conflicts among these objectives. In particular, a small number of additional tag SNPs can provide sufficient tolerance and balanced power given the low missing and error rates of today's genotyping platforms. AVAILABILITY: The software is freely available at Bioinformatics online and http://cilab.cs.ccu.edu.tw/service_dl.html.

Differential evolution (DE) has shown its effectiveness in solving many problems. The difference vector (DV), which serves as a measure for the dispersion of candidate solutions, has a key role in the adaptive mutation of DE. Traditionally, DE adopts one DV. In this paper, we investigate the use of more than one DV and propose the Poisson differential evolution (PDE) with a varying number of DVs based on Poisson distribution. Experimental results on 24 numerical benchmark functions point out the ineffectiveness of increasing DVs in the original DE. On the other hand, the results show that the proposed PDE can achieve significant improvement on DE in terms of solution quality and convergence speed, which validates the benefit of varying number of DVs for DE.

The problem of placing wireless transmitters to meet particular objectives, such as coverage and cost, has proven to be NP-hard. Furthermore, the heterogeneity of wireless networks makes the problem more intractable to deal with. This paper presents a novel multiobjective variable-length genetic algorithm to solve this problem. One does not need to determine the number of transmitters beforehand; the proposed algorithm simultaneously searches for the optimal number, types, and positions of heterogeneous transmitters by considering coverage, cost, capacity, and overlap. The proposed algorithm can achieve the optimal number of transmitters with coverage exceeding 98% on average for six benchmarks. These preferable experimental results demonstrate the high capability of the proposed algorithm for the wireless heterogeneous transmitter placement problem.

Extending the lifetime is a key issue in wireless sensor networks. An effective way to extend the lifetime is to partition the sensors into several covers and activate the covers one by one. Thus, the more the covers, the longer the lifetime. To find the maximum number of covers has been modeled as the Set K-Cover problem. In this paper we propose using order-based genetic algorithm to solve the Set K-Cover problem for extending the lifetime of wireless sensor networks. The proposed algorithm needs neither an upper bound nor any assumption about the maximum number of covers. Experimental results show that the order-based genetic algorithm can achieve near-optimal solutions efficiently.

To balance selection pressure and population diversity is a key issue of designing an effective genetic algorithm (GA). This paper proposes incorporating tabu search (TS) into GA to address the issue. Instead of running GA and TS by turns, the desirable strategy of TS is implanted in the survivor selection of GA as a filter for promising solutions. Consequently the selection pressure and population diversity of GA are controlled. Experimental results on six well-known test functions show that the proposed approach can outperform GA significantly in terms of solution quality. The empirical analysis further validates the effects of the TS strategy.

Wireless sensor network lifetime for large-scale surveillance systems is defined as the time span that all targets can be covered. One approach to extend the lifetime is to divide the deployed sensors into disjoint subsets of sensors, or sensor covers, such that each sensor cover can cover all targets and work by turns. The more sensor covers can be found, the longer sensor network lifetime can be prolonged. Finding the maximum number of sensor covers can be solved via transformation to the Disjoint Set Covers (DSC) problem, which has been proved to be NP-complete. For this optimization problem, existing heuristic algorithms either get unsatisfactory solutions in some cases or take exponential time complexity. This paper proposes a genetic algorithm to solve the DSC problem. The simulation results show that the proposed algorithm can get near-optimal solutions with polynomial computation time and can improve the performance of the most constrained-minimum constraining heuristic algorithm by 16% in solution quality.

Multi-parent crossover allows more than two parents participating in crossover. The increase of parents in crossover intensifies exploitation or exploration or both; however, the intensification is often unbalanced and consequently causes deterioration in performance. In this paper we propose the use of supermajority to address the issue of lopsided intensification on exploitation and exploration in multi-parent crossover. The proposed crossover, called biased occurrence based scanning crossover (bOB), controls the tendency toward exploitation or exploration by the threshold in supermajority. Two adaptive strategies are developed to adjust the threshold of bOB. Experimental results indicate that bOB can achieve significant improvement on uniform crossover and occurrence based scanning crossover in both solution quality and convergence speed. Precisely, the improvement in mean best fitness ranges from 4–89% on our test problems. The preferable results validate that bOB crossover can not only enhance the performance but also provide an effective way to control the exploitation and exploration in crossover.

An important scheme for extending sensor network lifetime is to divide sensor nodes into disjoint groups such that each group covers all targets and works alternatively. This scheme can be transformated to the Disjoint Set Covers (DSC) problem, which is proved to be NP-complete. Existing heuristic algorithms either get barely satisfactory solutions or take exponential time complexity. In this paper, we present a genetic algorithm to solve the DSC problem. Simulation results show that the proposed genetic algorithm can improve the most constrained-minimum constraining heuristic algorithm (MCMCC) in solution quality by $99\%$ with only polynomial computation time complexity.

This paper proposes a multi-parent crossover based on edge recombination. The original edge table is modified to record the adjacency information for more than two parents. Experimental results on the traveling salesman problem show the proposed multi-parent edge recombination is capable of enhancing edge recombination in solution quality.

We propose a new mutation operator - the biased mutation operator (BMO) -for evolution strategies, which is capable of handling problems for constrained fitness landscapes. The idea of our approach is to bias the mutation ellipsoid in relation to the parent and therefore lead the mutations into a beneficial direction self-adaptively. This helps to improve the success rate to reproduce better offspring. Experimental results show this bias enhances the solution quality within constrained search domains. The number of the additional strategy parameters used in our approach equals to the number of dimensions of the problem. Compared to the correlated mutation, the BMO needs much less memory and supersedes the computation of the rotation matrix of the correlated mutation and the asymmetric probability density function of the directed mutation.

This paper presents a Markov model for the convergence of multi-parent genetic algorithms (MPGAs). The proposed model formulates the variation of gene frequency caused by selection, multi-parent crossover, and mutation. In addition, it reveals the pair wise equivalence phenomenon in the number of parents and identifies the correlation between this number and the mean fitness in the OneMax problem. The good fit between theoretical and experimental results demonstrate the capability of this model. Moreover, the superiority of multi-parent crossover in convergence fitness over 2-parent crossover is validated theoretically as well as empirically.

No abstract available.

Multiparent crossovers have been validated their outperformance on several optimization problems. However, there are two issues to be considered - the number of parents and the disruptiveness caused by multiple parents. We present a tabu multiparent genetic algorithm (TMPGA) to address these two issues by integrating tabu search into the mating of multiparent genetic algorithms. TMPGA utilizes the tabu restriction and the aspiration criterion to sift selected parents in consideration of population diversity and selection pressure. Furthermore, the resulting mating validity further adjusts the number of parents participating in a mating. Experiments are conducted with four common test functions. The results indicate that TMPGA can achieve better performance than both two-parent GA and multiparent GA with the diagonal crossover.

Due to the entry of Taiwan into WTO and the recently liberalized Petroleum Management Law, the oil market in Taiwan is liberalized and thus is becoming more competitive. However, the space limitation and the residents' increasing awareness of environmental protection issues in the island make international vendors unavoidably have to rent tanks from domestic oil companies. In order to help the leaseholder maximize revenue by increasing the availability of tanks, an efficient maintenance scheduling is needed. This paper introduces a tabu-based genetic algorithm (TGA) and its implementation for solving a real-world maintenance scheduling problem of oil storage tanks. TGA incorporates a tabu list to prevent inbreeding and utilizes an aspiration criterion to supply moderate selection pressure so that the selection efficiency is improved, and the population diversity is maintained. The experimental results validate that TGA outperform GA in terms of solution quality and convergence efficiency. Keywords: Tabu-based genetic algorithm, maintenance scheduling, tabu search, genetic algorithm.

The genetic algorithm (GA) is a well-known heuristic optimization algorithm. However, it suffers from the serious problem of premature convergence, which is caused mainly by the population diversity decreasing in evolution. The authors propose a novel algorithm, called TGA, which integrates the memory structure and search strategy of Tabu Search (TS) with GA. As such, the selection efficiency is improved and the population diversity is maintained by incorporating the regeneration operator. The traveling salesman problem is used as a benchmark to evaluate TGA and compare it with GA and TS. Experimental results show that TGA achieves better performance than GA and TS in terms of both convergence speed and solution quality.