Estimating meme fitness in adaptive memetic algorithms for combinatorial problems

Among the most promising and active research areas in heuristic optimisation is the field of adaptive memetic algorithms (AMAs). These gain much of their reported robustness by adapting the probability with which each of a set of local improvement operators is applied, according to an estimate of their current value to the search process. This paper addresses the issue of how the current value should be estimated. Assuming the estimate occurs over several applications of a meme, we consider whether the extreme or mean improvements should be used, and whether this aggregation should be global, or local to some part of the solution space. To investigate these issues, we use the well-established COMA framework that coevolves the specification of a population of memes (representing different local search algorithms) alongside a population of candidate solutions to the problem at hand. Two very different memetic algorithms are considered: the first using adaptive operator pursuit to adjust the probabilities of applying a fixed set of memes, and a second which applies genetic operators to dynamically adapt and create memes and their functional definitions. For the latter, especially on combinatorial problems, credit assignment mechanisms based on historical records, or on notions of landscape locality, will have limited application, and it is necessary to estimate the value of a meme via some form of sampling. The results on a set of binary encoded combinatorial problems show that both methods are very effective, and that for some problems it is necessary to use thousands of variables in order to tease apart the differences between different reward schemes. However, for both memetic algorithms, a significant pattern emerges that reward based on mean improvement is better than that based on extreme improvement. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. The results also show that local reward schemes outperform global reward schemes in combinatorial spaces, unlike in continuous spaces. An analysis of evolving meme behaviour is used to explain these findings.     

A FORTRAN IV program for comparing ranking algorithms in quantitative biostratigraphy

A program for evaluating the performance of competing ranking algorithms in stratigraphic paleontology is presented. The program (1) generates a hypothetical, and thus known, succession of taxa in time and (2) simulates their succession in strata at several local sample sites. If desired, (1) and (2) may be repeated for several (=50 or 100 for example) iterations and the local site data for each sent to two user routines for inferred rankings (inferred succession of events in time). First data for first and last occurrences (fads and lads) taken together, then data for for lads-only, then data for fads-only is sent. For each submission of data to a user routine, Kendall rank correlation coefficients and Spearman coefficients are computed comparing the inferred rankings generated by the user routine with the known succession of events in time. The performance of two competing ranking algorithms may be compared by (1) obtaining for each submitted dataset the differences between corresponding Kendall (and/or Spearman) coefficients computed for the two algorithms, and (2) testing the observed differences for statistical significance. A simple two-sided t-test may be used to test whether the observed mean difference between two corresponding coefficients differs significantly from zero; if ct-tests are performed, the level of significance of each should be set to alpha/c to obtain a maximum experimentwise error rate of less than alpha. The program is used to compare three ranking algorithms provided by Agterberg and Nel (1982a, b) as well as to determine whether the algorithms work as well for datasets combining lads and fads vs datasets for lads-only or fads-only. Agterberg and Nel's Presorting algorithm performed better than their Ranking or Scaling algorithm. All three performed slightly but significantly better on data for lads-only or fads-only as opposed to combined data.     

Credit scoring algorithm based on link analysis ranking with support vector machine

Credit scoring is very important in business, especially in banks. We want to describe a person who is a good credit or a bad one by evaluating his/her credit. We systematically proposed three link analysis algorithms based on the preprocess of support vector machine, to estimate an applicant’s credit so as to decide whether a bank should provide a loan to the applicant. The proposed algorithms have two major phases which are called input weighted adjustor and class by support vector machine-based models. In the first phase, we consider the link relation by link analysis and integrate the relation of applicants through their information into input vector of next phase. In the other phase, an algorithm is proposed based on general support vector machine model. A real world credit dataset is used to evaluate the performance of the proposed algorithms by 10-fold cross-validation method. It is shown that the genetic link analysis ranking methods have higher performance in terms of classification accuracy.     

基于深度学习的目标检测算法综述

传统目标检测算法大多基于滑动窗口和人工特征提取,存在计算复杂度高和在复杂场景下鲁棒性差的缺点。近年来,研究人员将深度学习技术应用于目标检测领域,显著提高了算法性能。相比传统算法,基于深度学习的目标检测算法具有速度快、准确性高和在复杂条件下鲁棒性强的优点。从评价指标、公开数据集、传统算法框架等方面对目标检测任务进行阐述,按照是否存在显式的区域建议和是否定义先验锚框两种分类标准,对现有基于深度学习的目标检测算法进行分类,分别介绍算法的演进路线并总结算法机制、优势、局限性及适用场景。在此基础上,分析对比代表性算法在公开数据集中的表现,并对基于深度学习的目标检测的未来研究方向进行展望。     

水质遥感监测的关键要素叶绿素a的反演算法研究进展

叶绿素a浓度是表征水体富营养化程度的重要指标,通过遥感手段反演叶绿素a浓度是实现水体富营养化监测的一个有效途径,已衍生出了一系列叶绿素a浓度反演算法。这些算法各有所长,适用范围也各自有别。由于水体光学特征差异,盲目套用这些算法难以取得预期效果。为了推动水质遥感的进一步发展,从遥感反演的原理和数据源出发,对国内外利用遥感技术反演水体叶绿素a浓度的算法进行综述。根据算法结构设计的不同,将反演算法分为6大类,分别为荧光峰和反射峰算法、波段算法、指数算法、智能算法、基于水体分类的算法体系以及分析类算法,系统地梳理各类算法并分析算法特征。从算法适用的叶绿素a浓度区间和水体类型等角度出发,总结各类算法的适用范围,评述各类算法的优缺点,以期为环境和遥感工作者提供参考。主要结论如下：①Ⅱ类水体算法外推适应性较弱,应建立并补充实测数据集,研究各类水体光学特性异同点,构建基于水体分类的通用算法体系;②无人机技术与高光谱传感器的结合可为内陆水体水质监测提供新思路;③应结合机器学习算法与机理模型,发展物理原理约束的高精度反演模型。     

非对称AdaBoost算法及其在目标检测中的应用

针对目标检测中的非对称分类问题,在分析现有的由离散AdaBoost算法扩展得到的代价敏感(即非对称)学习算法的基础上,提出了以三个不同的非对称错误率上界为核心的推导非对称AdaBoost算法的统一框架. 在该框架下, 不仅现有离散型非对称AdaBoost算法之间的关系非常清晰, 而且其中不符合理论推导的部分可以很容易得到修正. 同时, 利用不同的优化方法, 最小化这三个不同上界, 推出了连续型AdaBoost算法的非对称扩展(用Asym-Real AdaBoost和Asym-Gentle AdaBoost 表示). 新的算法不仅在弱分类器组合系数的计算上比现有离散型算法更加方便, 而且实验证明, 在人脸检测和行人检测两方面都获得了比传统对称AdaBoost算法和离散型非对称AdaBoost算法更好的性能.     

Comparison of Stochastic Global Optimization Methods to Estimate Neural Network Weights

Training a neural network is a difficult optimization problem because of numerous local minima. Many global search algorithms have been used to train neural networks. However, local search algorithms are more efficient with computational resources, and therefore numerous random restarts with a local algorithm may be more effective than a global algorithm. This study uses Monte-Carlo simulations to determine the efficiency of a local search algorithm relative to nine stochastic global algorithms when using a neural network on function approximation problems. The computational requirements of the global algorithms are several times higher than the local algorithm and there is little gain in using the global algorithms to train neural networks. Since the global algorithms only marginally outperform the local algorithm in obtaining a lower local minimum and they require more computational resources, the results in this study indicate that with respect to the specific algorithms and function approximation problems studied, there is little evidence to show that a global algorithm should be used over a more traditional local optimization routine for training neural networks. Further, neural networks should not be estimated from a single set of starting values whether a global or local optimization method is used.     

Experimental Study on Strategy of CombiningSAT Algorithms

The effectiveness of many SAT algorithms is mainly reflected by their significant performances on one or several classes of specific SAT problems.Different kinds of SAT algorithms all have their own hard instances respectively.Therefore,to get the better performance on all kinds of problems,SAT solver should know how to select different algorithms according to the feature of instances.In this paper the differences of several effective SAT algorithms are analyzed and two new parameters φand δ are proposed to characterize the feature of SAT instances.Experiments are performed to study the relationship between SAT algorithms and some statistical parameters including φ，δ.Based on this analysis,a strategy is presented for designing a faster SAT tester by carefully combining some existing SAT algorithms.With this strategy,a faster SAT tester to solve many kinds of SAT problem is obtained.     

Adaptive location policies for global scheduling

Two important components of a global scheduling algorithm are its transfer policy and its location policy. While the transfer policy determines whether a task should be transferred, the location policy determines where it should be transferred. Based on their location policies, global scheduling algorithms can be broadly classified as receiver-initiated, sender-initiated, or symmetrically-initiated. The relative performance of these classes of algorithms has been shown to depend on the system workload. We present two adaptive location policies for global scheduling in distributed systems. These location policies are general, and can be used in conjunction with many existing transfer policies. By adapting to the system workload, the proposed policies capture the advantages of both sender-initiated and receiver-initiated policies. In addition, by adaptively directing their search activities toward the nodes that are most likely to be suitable counterparts in task transfers, the proposed policies provide short transfer latency and low overhead, and more important, high probability of finding a suitable counterpart if one exists. These properties allow these policies to deliver good performance over a very wide range of system operating conditions. The proposed policies are compared with nonadaptive policies, and are shown to considerably improve performance and to avoid causing system instability     

Multi-path based Algorithms for Data Transfer in the Grid Environment

This paper introduces two alternative algorithms for efficient data transfer in the Grid environment. For data transfer from a source node to the destination node, the algorithms can construct multiple dynamic paths by selecting some other nodes as data relays. The bandwidth available in different paths can be aggregated thus to significantly speed up the data transfer process. The proposed algorithms differ from each other in whether the global networking information should be considered. Experimental results indicate that both algorithms can provide efficient data transfer under various circumstances.