摘要 :
Vertex cover is one of the best known NP-Hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A...
展开
Vertex cover is one of the best known NP-Hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A theoretical analysis that explains these empirical results is presented concerning the random local search algorithm and the ${ (1+1)}$-EA. Since it is not expected that an algorithm can solve the vertex cover problem in polynomial time, a worst case approximation analysis is carried out for the two considered algorithms and comparisons with the best known problem-specific ones are presented. By studying instance classes of the problem, general results are derived. Although arbitrarily bad approximation ratios of the ${ (1+1)}$-EA can be proved for a bipartite instance class, the same algorithm can quickly find the minimum cover of the graph when a restart strategy is used. Instance classes where multiple runs cannot considerably improve the performance of the ${ (1+1)}$-EA are considered and the characteristics of the graphs that make the optimization task hard for the algorithm are investigated and highlighted. An instance class is designed to prove that the ${ (1+1)}$-EA cannot guarantee better solutions than the state-of-the-art algorithm for vertex cover if worst cases are considered. In particular, a lower bound for the worst case approximation ratio, slightly less than two, is proved. Nevertheless, there are subclasses of the vertex cover problem for which the ${ (1+1)}$-EA is efficient. It is proved that if the vertex degree is at most two, then the algorithm can solve the problem in polynomial tim-
e.
收起
摘要 :
Games have long played an important role in the development and understanding of coevolutionary learning systems. In particular, the search process in coevolutionary learning is guided by strategic interactions between solutions ...
展开
Games have long played an important role in the development and understanding of coevolutionary learning systems. In particular, the search process in coevolutionary learning is guided by strategic interactions between solutions in the population, which can be naturally framed as game playing. We study two important issues in coevolutionary learning—generalization performance and diversity—using games. The first one is concerned with the coevolutionary learning of strategies with high generalization performance, that is, strategies that can outperform against a large number of test strategies (opponents) that may not have been seen during coevolution. The second one is concerned with diversity levels in the population that may lead to the search of strategies with poor generalization performance. It is not known if there is a relationship between generalization and diversity in coevolutionary learning. This paper investigates whether there is such a relationship in coevolutionary learning through a detailed empirical study. We systematically investigate the impact of various diversity maintenance approaches on the generalization performance of coevolutionary learning quantitatively using case studies. The problem of the iterated prisoner's dilemma (IPD) game is considered. Unlike past studies, we can measure both the generalization performance and the diversity level of the population of evolved strategies. Results from our case studies show that the introduction and maintenance of diversity do not necessarily lead to the coevolutionary learning of strategies with high generalization performance. However, if individual strategies can be combined (e.g., using a gating mechanism), there is the potential of exploiting diversity in coevolutionary learning to improve generalization performance. Specifically, when the introduction and maintenance of diversity lead to a speciated population during coevolution, where each specialist strategy is capab-
le of outperforming different opponents, the population as a whole can have a significantly higher generalization performance compared to individual strategies.
收起
摘要 :
Negative correlation learning (NCL) is a neural network ensemble learning algorithm that introduces a correlation penalty term to the cost function of each individual network so that each neural network minimizes its mean square ...
展开
Negative correlation learning (NCL) is a neural network ensemble learning algorithm that introduces a correlation penalty term to the cost function of each individual network so that each neural network minimizes its mean square error (MSE) together with the correlation of the ensemble. This paper analyzes NCL and reveals that the training of NCL (when $lambda=1$) corresponds to training the entire ensemble as a single learning machine that only minimizes the MSE without regularization. This analysis explains the reason why NCL is prone to overfitting the noise in the training set. This paper also demonstrates that tuning the correlation parameter $lambda$ in NCL by cross validation cannot overcome the overfitting problem. The paper analyzes this problem and proposes the regularized negative correlation learning (RNCL) algorithm which incorporates an additional regularization term for the whole ensemble. RNCL decomposes the ensemble's training objectives, including MSE and regularization, into a set of sub-objectives, and each sub-objective is implemented by an individual neural network. In this paper, we also provide a Bayesian interpretation for RNCL and provide an automatic algorithm to optimize regularization parameters based on Bayesian inference. The RNCL formulation is applicable to any nonlinear estimator minimizing the MSE. The experiments on synthetic as well as real-world data sets demonstrate that RNCL achieves better performance than NCL, especially when the noise level is nontrivial in the data set.
收起
摘要 :
The capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable to small instances, heuristi...
展开
The capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable to small instances, heuristic and metaheuristic methods are widely adopted when solving CARP. In this paper, we propose a memetic algorithm, namely memetic algorithm with extended neighborhood search (MAENS), for CARP. MAENS is distinct from existing approaches in the utilization of a novel local search operator, namely Merge-Split (MS). The MS operator is capable of searching using large step sizes, and thus has the potential to search the solution space more efficiently and is less likely to be trapped in local optima. Experimental results show that MAENS is superior to a number of state-of-the-art algorithms, and the advanced performance of MAENS is mainly due to the MS operator. The application of the MS operator is not limited to MAENS. It can be easily generalized to other approaches.
收起
摘要 :
In this paper, a sparse learning algorithm, probabilistic classification vector machines (PCVMs), is proposed. We analyze relevance vector machines (RVMs) for classification problems and observe that adopting the same prior for d...
展开
In this paper, a sparse learning algorithm, probabilistic classification vector machines (PCVMs), is proposed. We analyze relevance vector machines (RVMs) for classification problems and observe that adopting the same prior for different classes may lead to unstable solutions. In order to tackle this problem, a signed and truncated Gaussian prior is adopted over every weight in PCVMs, where the sign of prior is determined by the class label, i.e., $+$1 or $-$1. The truncated Gaussian prior not only restricts the sign of weights but also leads to a sparse estimation of weight vectors, and thus controls the complexity of the model. In PCVMs, the kernel parameters can be optimized simultaneously within the training algorithm. The performance of PCVMs is extensively evaluated on four synthetic data sets and 13 benchmark data sets using three performance metrics, error rate (ERR), area under the curve of receiver operating characteristic (AUC), and root mean squared error (RMSE). We compare PCVMs with soft-margin support vector machines (SVM$_{rm Soft}$), hard-margin support vector machines (SVM$_{rm Hard}$), SVM with the kernel parameters optimized by PCVMs (SVM $_{rm PCVM}$), relevance vector machines (RVMs), and some other baseline classifiers. Through five replications of twofold cross-validation $F$ test, i.e., 5 $times$ 2 cross-validation $F$ test, over single data sets and Friedman test with the corresponding post-hoc test to compar-
-
e these algorithms over multiple data sets, we notice that PCVMs outperform other algorithms, including SVM $_{rm Soft}$, SVM $_{rm Hard}$, RVM, and SVM $_{rm PCVM}$, on most of the data sets under the three metrics, especially under AUC. Our results also reveal that the performance of SVM$_{rm PCVM}$ is slightly better than SVM $_{rm Soft}$, implying that the parameter optimization algorithm in PCVMs is better than cross validation in terms of performance and computational complexity. In this paper, we also discuss the superiority of PCVMs' formulation using maximum a posteriori (MAP) analysis and margin analysis, which explain the empirical success of PCVMs.
收起
摘要 :
The choice of the materials used as the dielectric media in large transformers continues to be a combination of pressboard and mineral oil. However, a number of failures in the field have been attributed to the surface discharge o...
展开
The choice of the materials used as the dielectric media in large transformers continues to be a combination of pressboard and mineral oil. However, a number of failures in the field have been attributed to the surface discharge or creeping discharge over the oil/pressboard interface. This paper reports on an experiment to study surface discharge over oil/pressboard. The TJ (triple-junction) model was used to study the characteristic of partial discharge (PD) from inception to flashover. The max PD charge, pattern, frequency and current pulse were measured during the flashover process. Four oil/pressboard specimens with different aging degrees were used and their influence on the flashover process over oil/paper interface was studied in this experiment. The results indicate that the max PD charge and PD frequency increase with the increase of applied voltage. The oil aging has great influence while the pressboard aging has little influence on PD characteristic over oil/pressboard. The PD pattern and current pulse shape show great difference for various applied voltages. The results therefore suggest that the PD detection on the oil/pressboard can be used effectively to implement the early monitor of surface discharge thereby to avoid the formation of surface flashover.
收起
