Grammatical inference by hill climbing

A cost function is developed, based on information-theoretic concepts, that measures the complexity of a stochastic context-free grammar, as well as the discrepancy between its language and a given stochastic language sample. This function is used to guide a search procedure that finds simple grammars whose languages are good fits to a sample. Reasonable results have been obtained in a variety of cases, including parenthesis and addition strings, Basic English (the first 25 sentences in English Through Pictures) and chain-encoded chromosome boundaries.     

A comparison of generalized linear discriminant analysis algorithms

Linear discriminant analysis (LDA) is a dimension reduction method which finds an optimal linear transformation that maximizes the class separability. However, in undersampled problems where the number of data samples is smaller than the dimension of data space, it is difficult to apply LDA due to the singularity of scatter matrices caused by high dimensionality. In order to make LDA applicable, several generalizations of LDA have been proposed recently. In this paper, we present theoretical and algorithmic relationships among several generalized LDA algorithms and compare their computational complexities and performances in text classification and face recognition. Towards a practical dimension reduction method for high dimensional data, an efficient algorithm is proposed, which reduces the computational complexity greatly while achieving competitive prediction accuracies. We also present nonlinear extensions of these LDA algorithms based on kernel methods. It is shown that a generalized eigenvalue problem can be formulated in the kernel-based feature space, and generalized LDA algorithms are applied to solve the generalized eigenvalue problem, resulting in nonlinear discriminant analysis. Performances of these linear and nonlinear discriminant analysis algorithms are compared extensively.     

Learning exponential state-growth languages by hill climbing

Training recurrent neural networks on infinite state languages has been successful with languages in which the minimal number of machine states grows linearly with the length of the sentence, but has faired poorly with exponential state-growth languages. The new architecture learns several exponential state-growth languages in near perfect by hill climbing.     

用爬山法实现无中心式网格调度

为方便网格资源的扩展,网格调度应当是无中心的.为在尽可能多的计算资源中为单地点作业优化资源选择,这里采用了爬山算法.当一个网格调度器收到一个单地点作业,爬山法被激活,根据网格调度器之间的相邻关系为作业找出最适合的计算系统,这里每个计算系统的适合度用预测的作业响应时间表示.实验模拟了无中心式网格调度与计算系统之间的性能差别,每个计算系统的本地调度采用保守式装填法,网格工作负荷由模型得到,并用一段工作负荷的平均响应时间衡量调度性能.实验结果表明,即使在作业提交点分布不均匀且运行时间估计不准确情况下,爬山法仍可有效改善单地点作业的调度.     

Cryptanalysis of Enigma double indicators with hill climbing

The Enigma machines were a series of electromechanical rotor cipher machines developed in Germany and used in the first half of the twentieth century to protect commercial, diplomatic, and military communications. Until 1938, the German Army used the so-called double-indicator procedure to transmit Enigma-encoded messages. It was replaced in September 1938 by a new procedure also involving double indicators. Both procedures enabled a team of mathematicians from the Polish Cipher Bureau to recover the wiring of the rotors and to develop cryptanalytic methods for the recovery of the daily keys. The double-indicator procedure was discontinued by the German Army in May 1940, and new methods were developed by the British at Bletchley Park, who were assisted by the knowledge transferred to them by the Polish cryptanalysts. In this article, the authors introduce two new algorithms that build on the historical cryptanalytic attacks on the two variants of the double-indicator procedures. Those attacks are based on hill climbing, divide-and-conquer, and specialized scoring functions, and they can recover the daily key using a number of indicators significantly smaller than the number of indicators required for the historical methods. Unlike the historical methods, the new algorithms produce unique and unambiguous results, including for scenarios with turnover of the middle rotor, and they also fully recover the plugboard settings. With these algorithms we won an international Enigma contest organized in 2015 by the City of Poznan, in memory of the Polish Cipher Bureau mathematicians.     

A cognitive heuristic algorithm for reseau mark detection by hill climbing

A hill-climbing approach for the automatic detection of Reseau marks (RM) on the vidicon type of imagery is presented. This procedure is based on the minimization of a figure of merit which is a measure of the clustering nature of the gray values of the Reseau pixels around a nominal value. The often-encountered problem of false detection is circumvented by incorporating the concept of ``learning' the mean gray value of the RM pixels. Results of applying the algorithm to both synthetic and actual imagery demonstrate the efficacy of the proposed method.     

K-means-type algorithms: a generalized convergence theorem and characterization of local optimality

The K-means algorithm is a commonly used technique in cluster analysis. In this paper, several questions about the algorithm are addressed. The clustering problem is first cast as a nonconvex mathematical program. Then, a rigorous proof of the finite convergence of the K-means-type algorithm is given for any metric. It is shown that under certain conditions the algorithm may fail to converge to a local minimum, and that it converges under differentiability conditions to a Kuhn-Tucker point. Finally, a method for obtaining a local-minimum solution is given.     

一种广义次成分提取算法及其收敛性分析

广义次成分分析(generalized minor component analysis,GMCA)在现代信号处理的许多领域具有重要作用.目前现有的大多算法不能同时具备与算法对应的信息准则,以及收敛性、自稳定性和多个广义次成分提取的性能.针对上述问题,利用一种新的信息传播规则,推导出一种广义次成分提取算法,并采用确定离散时间方法(deterministic discrete time,DDT)对算法的全局收敛性能进行分析;同时,通过理论分析算法的收敛性能与算法初始状态的关系,表明算法具有自稳定性.进一步地,探索了算法在多重广义次成分提取方面的应用.相比之前的算法,所提算法具有更快的收敛速度.Matlab仿真验证了所提出算法的各项性能.     

Fast forward planning by guided enforced hill climbing

In recent years, a number of new heuristic search methods have been developed in the field of automated planning. Enforced hill climbing (EHC) is one such method which has been frequently used in a number of AI planning systems. Despite certain weaknesses, such as getting trapped in dead-ends in some domains, this method is more competitive than several other methods in many planning domains. In order to enhance the efficiency of ordinary enforced hill climbing, a new form of enforced hill climbing, called guided enforced hill climbing, is introduced in this paper. An adaptive branch ordering function is the main feature that guided enforced hill climbing has added to EHC. Guided enforced hill climbing expands successor states in the order recommended by the ordering function. Our experimental results in several planning domains show a significant improvement in the efficiency of the enforced hill climbing method, especially when applied to larger problems.     

Local convergence analysis of FastICA and related algorithms

The FastICA algorithm is one of the most prominent methods to solve the problem of linear independent component analysis (ICA). Although there have been several attempts to prove local convergence properties of FastICA, rigorous analysis is still missing in the community. The major difficulty of analysis is because of the well-known sign-flipping phenomenon of FastICA, which causes the discontinuity of the corresponding FastICA map on the unit sphere. In this paper, by using the concept of principal fiber bundles, FastICA is proven to be locally quadratically convergent to a correct separation. Higher order local convergence properties of FastICA are also investigated in the framework of a scalar shift strategy. Moreover, as a parallelized version of FastICA, the so-called QR FastICA algorithm, which employs the QR decomposition (Gram-Schmidt orthonormalization process) instead of the polar decomposition, is shown to share similar local convergence properties with the original FastICA.     

Modeling and convergence analysis of distributed coevolutionary algorithms

A theoretical foundation is presented for modeling and convergence analysis of a class of distributed coevolutionary algorithms applied to optimization problems in which the variables are partitioned among p nodes. An evolutionary algorithm at each of the p nodes performs a local evolutionary search based on its own set of primary variables, and the secondary variable set at each node is clamped during this phase. An infrequent intercommunication between the nodes updates the secondary variables at each node. The local search and intercommunication phases alternate, resulting in a cooperative search by the p nodes. First, we specify a theoretical basis for a class of centralized evolutionary algorithms in terms of construction and evolution of sampling distributions over the feasible space. Next, this foundation is extended to develop a model for a class of distributed coevolutionary algorithms. Convergence and convergence rate analyzes are pursued for basic classes of objective functions. Our theoretical investigation reveals that for certain unimodal and multimodal objectives, we can expect these algorithms to converge at a geometrical rate. The distributed coevolutionary algorithms are of most interest from the perspective of their performance advantage compared to centralized algorithms, when they execute in a network environment with significant local access and internode communication delays. The relative performance of these algorithms is therefore evaluated in a distributed environment with realistic parameters of network behavior.     

A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems

Dynamic optimization problems challenge traditional evolutionary algorithms seriously since they, once converged, cannot adapt quickly to environmental changes. This paper investigates the application of memetic algorithms, a class of hybrid evolutionary algorithms, for dynamic optimization problems. An adaptive hill climbing method is proposed as the local search technique in the framework of memetic algorithms, which combines the features of greedy crossover-based hill climbing and steepest mutation-based hill climbing. In order to address the convergence problem, two diversity maintaining methods, called adaptive dual mapping and triggered random immigrants, respectively, are also introduced into the proposed memetic algorithm for dynamic optimization problems. Based on a series of dynamic problems generated from several stationary benchmark problems, experiments are carried out to investigate the performance of the proposed memetic algorithm in comparison with some peer evolutionary algorithms. The experimental results show the efficiency of the proposed memetic algorithm in dynamic environments.     

A proof of convergence for Ant algorithms

A proof of convergence for Ant algorithms is developed. Ant algorithms were modeled as branching random processes: the branching random walk and branching Wiener process to derive rates of birth and death of ant paths. Substitution is then carried out in birth–death processes which proves that a stable distribution is surely reached. This indicates that Ant algorithms converge with probability one. This analogy models Ant algorithms complexity parameters such as the number of cycles, the degrees of freedom of problem and the number of ants.     

A perspective on convergence of adaptive control algorithms

This paper presents an overview of the current status of convergence theory for adaptive control algorithms. Rather than giving a comprehensive survey, the paper aims to emphasize the conceptual common ground between different approaches. Possible areas for future research are also discussed.     

A study on the convergence of genetic algorithms

This paper extends genetic algorithms to achieve fast solutions to difficult problem. To accomplish this, we present empirical results on the terminated condition by bias and the functionized model of mutation rate in genetic algorithms. The terminated condition by bias enable to reducing computation time(CPU time) according to limitted and pre-estimated number of generations. The functionized model of mutation operator reducing computation time and improving solution should be accomplished by applying quite low mutation rate on the continuing generation with remaining 95 percentage of bias.     

An approach of feature selection using graph-theoretic heuristic and hill climbing

Pattern Analysis and Applications - Search-based methods that use matrix- or vector-based representations of the dataset are commonly employed to solve the problem of feature selection. These...     

基于组合式爬山算法提高S盒非线性度的方法

针对三点和四点爬山算法对随机置换盒(S盒)的非线性度进行优化时计算量大及效率低的问题,提出了一种组合式爬山算法(CHC)。该算法把交换S盒两个输出数据的行为定义为一个交换元,利用加权择优函数,筛选出若干个对非线性度的提升贡献较大的交换元,然后通过同时应用多个交换元,达成提高S盒非线性度的目标。实验中利用CHC算法,一次最多交换了12个输出数据,使得大部分8输入8输出随机S盒的非线性度超过了102,最高可达106。实验结果表明,所提出的CHC算法相比于三点和四点爬山算法,不仅降低了计算量,而且对随机S盒的非线性度也有着更为明显的提升作用。     

A generalized scheme for mapping parallel algorithms

A generalized mapping strategy that uses a combination of graph theory, mathematical programming, and heuristics is proposed. The authors use the knowledge from the given algorithm and the architecture to guide the mapping. The approach begins with a graphical representation of the parallel algorithm (problem graph) and the parallel computer (host graph). Using these representations, the authors generate a new graphical representation (extended host graph) on which the problem graph is mapped. An accurate characterization of the communication overhead is used in the objective functions to evaluate the optimality of the mapping. An efficient mapping scheme is developed which uses two levels of optimization procedures. The objective functions include minimizing the communication overhead and minimizing the total execution time which includes both computation and communication times. The mapping scheme is tested by simulation and further confirmed by mapping a real world application onto actual distributed environments     

Linear convergence of generalized Weiszfeld's method

Weiszfeld's method is widely used for solving problems of optimal location. It is shown that a very general variant of this method converges linearly thus generalizing a result of I. N. Katz.