Logic-based genetic programming with definite clause translation grammars

DCTG-GP is a genetic programming system that uses definite clause translation grammars. A DCTG is a logical version of an attribute grammar that supports the definition of context-free languages, and it allows semantic information associated with a language to be easily accommodated by the grammar. This is useful in genetic programming for defining the interpreter of a target language, or incorporating both syntactic and semantic problem-specific constraints into the evolutionary search. The DCTG-GP system improves on other grammar-based GP systems by permitting nontrivial semantic aspects of the language to be defined with the grammar. It also automatically analyzes grammar rules in order to determine their minimal depth and termination characteristics, which are required when generating random program trees of varied shapes and sizes. An application using DCTG-GP is described. Brian James Ross, Ph.D.: He is an associate professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his MSc at the University of British Columbia, Canada, in 1988, and his PhD at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, machine learning, language induction, concurrency, and logic programming.     

A comparison of bloat control methods for genetic programming

Genetic programming has highlighted the problem of bloat, the uncontrolled growth of the average size of an individual in the population. The most common approach to dealing with bloat in tree-based genetic programming individuals is to limit their maximal allowed depth. An alternative to depth limiting is to punish individuals in some way based on excess size, and our experiments have shown that the combination of depth limiting with such a punitive method is generally more effective than either alone. Which such combinations are most effective at reducing bloat? In this article we augment depth limiting with nine bloat control methods and compare them with one another. These methods are chosen from past literature and from techniques of our own devising. esting with four genetic programming problems, we identify where each bloat control method performs well on a per-problem basis, and under what settings various methods are effective independent of problem. We report on the results of these tests, and discover an unexpected winner in the cross-platform category.     

Neutral offspring controlling operators in genetic programming

Code bloat, one of the main issues of genetic programming (GP), slows down the search process, destroys program structures, and exhausts computer resources. To deal with these issues, two kinds of neutral offspring controlling operators are proposed—non-neutral offspring (NNO) operators and non-larger neutral offspring (NLNO) operators. Two GP benchmark problems—symbolic regression and 11-multiplexer—are used to test the new operators. Experimental results indicate that NLNO is able to confine code bloat significantly and improve performance simultaneously, which NNO cannot do.     

A dynamic programming approximation for downlink channel allocation in cognitive femtocell networks

Both femtocells and cognitive radio (CR) are envisioned as promising technologies for the NeXt Generation (xG) cellular networks. Cognitive femtocell networks (CogFem) incorporate CR technology into femtocell deployment to reduce its demand for more spectrum bands, thereby improving the spectrum utilization. In this paper, we focus on the channel allocation problem in CogFem, and formulate it as a stochastic dynamic programming (SDP) problem aiming at optimizing the long-term cumulative system throughput of individual femtocells. However, the multi-dimensional state variables resulted from complex exogenous stochastic information make the SDP problem computationally intractable using standard value iteration algorithms. To address this issue, we propose an approximate dynamic programming (ADP) algorithm in pursuit of an approximate solution to the SDP problem. The proposed ADP algorithm relies on an efficient value function approximation (VFA) architecture that we design and a stochastic gradient learning strategy to function, enabling each femtocell to learn and improve its own channel allocation policy. The algorithm is computationally attractive for large-scale downlink channel allocation problems in CogFem since its time complexity does not grow exponentially with the number of femtocells. Simulation results have shown that the proposed ADP algorithm exhibits great advantages: (1) it is feasible for online implementation with a fair rate of convergence and adaptability to both long-term and short-term network dynamics; and (2) it produces high-quality solutions fast, reaching approximately 80% of the upper bounds provided by optimal backward dynamic programming (DP) solutions to a set of deterministic counterparts of the formulated SDP problem.     

A comparison of boundary graph grammars and context-free hypergraph grammars

Context-free hypergraph grammars and boundary graph grammars of bounded nonterminal degree have the same power, both for generating sets of graphs and for generating sets of hypergraphs. Arbitrary boundary graph grammars have more graph generating power than context-free hypergraph grammars, but they have the same hypergraph generating power. To obtain these results, several normal forms for boundary graph grammars are given. It is also shown that the class of boundary graph languages is closed under the operation of edge contraction, where the label of the edge indicates whether or not the edge should be contracted.     

A multiobjective genetic algorithm for obtaining the optimal size of a recurrent neural network for grammatical inference

Grammatical inference has been extensively studied in recent years as a result of its wide field of application, and in turn, recurrent neural networks have proved themselves to be a good tool for grammatical inference. The learning algorithms for these neural networks, however, have been far less studied than those for feed-forward neural networks. Classical training methods for recurrent neural networks suffer from being trapped in local minimal and having a high computational time. In addition, selecting the optimal size of a neural network for a particular application is a difficult task. This suggests that the problems of developing methods to determine optimal topologies and new training algorithms should be studied.In this paper, we present a multi-objective evolutionary algorithm which is able to determine the optimal size of recurrent neural networks in any particular application. This is specially analyzed in the case of grammatical inference: in particular, we study how to establish the optimal size of a recurrent neural network in order to learn positive and negative examples in a certain language, and how to determine the corresponding automaton using a self-organizing map once the training has been completed.     

Inference for transition network grammars

This paper gives a brief introduction to transition networks and proposes an approach to the inference of transition network grammars.     

Generating valid grammar-based test inputs by means of genetic programming and annotated grammars

Automated generation of system level tests for grammar based systems requires the generation of complex and highly structured inputs, which must typically satisfy some formal grammar. In our previous work, we showed that genetic programming combined with probabilities learned from corpora gives significantly better results over the baseline (random) strategy. In this work, we extend our previous work by introducing grammar annotations as an alternative to learned probabilities, to be used when finding and preparing the corpus required for learning is not affordable. Experimental results carried out on six grammar based systems of varying levels of complexity show that grammar annotations produce a higher number of valid sentences and achieve similar levels of coverage and fault detection as learned probabilities.     

A genetic network programming with learning approach for enhanced stock trading model

In this paper, an enhancement of stock trading model using Genetic Network Programming (GNP) with Sarsa Learning is described. There are three important points in this paper: First, we use GNP with Sarsa Learning as the basic algorithm while both Technical Indices and Candlestick Charts are introduced for efficient stock trading decision-making. In order to create more efficient judgment functions to judge the current stock price appropriately, Importance Index (IMX) has been proposed to tell GNP the timing of buying and selling stocks. Second, to improve the performance of the proposed GNP-Sarsa algorithm, we proposed a new method that can learn the appropriate function describing the relation between the value of each technical index and the value of the IMX. This is an important point that devotes to the enhancement of the GNP-Sarsa algorithm. The third point is that in order to create more efficient judgment functions, sub-nodes are introduced in each node to select appropriate stock price information depending on the situations and to determine appropriate actions (buying/selling). To confirm the effectiveness of the proposed method, we carried out the simulation and compared the results of GNP-Sarsa with other methods like GNP with Actor Critic, GNP with Candlestick Chart, GA and Buy&Hold method. The results shows that the stock trading model using GNP-Sarsa outperforms all the other methods.     

Modular neural network programming with genetic optimization

This study proposes a modular neural network (MNN) that is designed to accomplish both artificial intelligent prediction and programming. Each modular element adopts a high-order neural network to create a formula that considers both weights and exponents. MNN represents practical problems in mathematical terms using modular functions, weight coefficients and exponents. This paper employed genetic algorithms to optimize MNN parameters and designed a target function to avoid over-fitting. Input parameters were identified and modular function influences were addressed in manner that significantly improved previous practices. In order to compare the effectiveness of results, a reference study on high-strength concrete was adopted, which had been previously studied using a genetic programming (GP) approach. In comparison with GP, MNN calculations were more accurate, used more concise programmed formulas, and allowed the potential to conduct parameter studies. The proposed MNN is a valid alternative approach to prediction and programming using artificial neural networks.     

A model of portfolio optimization using time adapting genetic network programming

This paper describes a decision-making model of dynamic portfolio optimization for adapting to the change of stock prices based on an evolutionary computation method named genetic network programming (GNP). The proposed model, making use of the information from technical indices and candlestick chart, is trained to generate portfolio investment advice. Experimental results on the Japanese stock market show that the decision-making model using time adapting genetic network programming (TA-GNP) method outperforms other traditional models in terms of both accuracy and efficiency. A comprehensive analysis of the results is provided, and it is clarified that the TA-GNP method is effective on the portfolio optimization problem.     

Modifying genetic programming for artificial neural network development for data mining

The development of artificial neural networks (ANNs) is usually a slow process in which the human expert has to test several architectures until he finds the one that achieves best results to solve a certain problem. However, there are some tools that provide the ability of automatically developing ANNs, many of them using evolutionary computation (EC) tools. One of the main problems of these techniques is that ANNs have a very complex structure, which makes them very difficult to be represented and developed by these tools. This work presents a new technique that modifies genetic programming (GP) so as to correctly and efficiently work with graph structures in order to develop ANNs. This technique also allows the obtaining of simplified networks that solve the problem with a small group of neurons. In order to measure the performance of the system and to compare the results with other ANN development methods by means of evolutionary computation (EC) techniques, several tests were performed with problems based on some of the most used test databases in the Data Mining domain. These comparisons show that the system achieves good results that are not only comparable to those of the already existing techniques but, in most cases, improve them.     

The structure of the genetic programming collaboration network

The genetic programming bibliography aims to be the most complete reference of papers on genetic programming. In addition to locating publications, it contains coauthor and coeditor relationships which have not previously been studied. These reveal some similarities and differences between our field and collaborative social networks in other scientific fields.

A comparison of linear genetic programming and neural networks inmedical data mining

We introduce a new form of linear genetic programming (GP). Two methods of acceleration of our GP approach are discussed: 1) an efficient algorithm that eliminates intron code and 2) a demetic approach to virtually parallelize the system on a single processor. Acceleration of runtime is especially important when operating with complex data sets, because they are occurring in real-world applications. We compare GP performance on medical classification problems from a benchmark database with results obtained by neural networks. Our results show that GP performs comparably in classification and generalization     

一种基于改进遗传算法的无线网络覆盖研究

将改进的遗传算法运用到无线传感器网络节点最优覆盖问题上,通过设置合理的接入访问点位置,可以实现网络有效覆盖率的最大化,并有效避免小区间的同频干扰。基于遗传算法以网络有效覆盖率为优化目标,改进了遗传算法中的交叉和变异策略。实验表明,改进的遗传算法可有效提高网络的覆盖率,实现了网络性能优化。     

A comparison of network and hierarchical data management in large programming projects

A number of programming languages are studied to compare their techniques for data management in large programs. In particular, it is argued that the hierarchical scope rules of Pascal violate accepted criteria for large program design. FORTRAN is shown to obey these criteria in its global data rules only. To support this, large programs in the two languages are studied in detail. There is no intention to provide statistical arguments, but rather these detailed case studies show the nature of programming style that can and cannot be supported by the languages used. Finally, the problems identified in the case studies are used to examine the suitability of a number of other programming languages with regard to data management in large projects.     

A system for programming and controlling sensor-based robot manipulators

This paper describes an approach to programming and controlling robot manipulators which facilitates the use of sensory information. Robot actions are specified by declaring software servo processes which control the robot's various degrees of freedom. These servo processes can involve position, orientation, force, and torque information from the robot itself, or data from external sensors. Robot tasks are programmed by dynamically modifying the servo processes or by changing set points to these processes. Condition monitors, which have access to program and sensory information, detect the completion of program steps.     

A comparison of programming languages for software engineering

Four programming languages (Fortran, Cobol, Jovial and the proposed DoD standard) are compared in the light of modern ideas of good software engineering practice. The comparison begins by identifying a core for each language that captures the essential properties of the language and the intent of the language designers. These core languages then serve as a basis for the discussion of the language philosophies and the impact of the language on gross program organization and on the use of individual statements.     

一种基于改进遗传规划的泛函网络结构逼近模型

基于泛函网络的结构特点和遗传规划的全局搜索能力,提出了广义基函数概念,通过改进遗传规划的编码方式对广义基函数进行学习,用最小二乘法设计适应度函数,从而确定泛函网络的最佳逼近结构模型。最后,4个数值仿真实例表明,该方法是有效可行的,具有较强的泛化特性。