An experimental study of adaptive control for evolutionary algorithms

In this paper, we investigate how adaptive operator selection techniques are able to efficiently manage the balance between exploration and exploitation in an evolutionary algorithm, when solving combinatorial optimization problems. We introduce new high level reactive search strategies based on a generic algorithm's controller that is able to schedule the basic variation operators of the evolutionary algorithm, according to the observed state of the search. Our experiments on SAT instances show that reactive search strategies improve the performance of the solving algorithm.     

Decision making policy for RF energy harvesting enabled cognitive radios in decentralized wireless networks

Cognitive radio (CR) paradigm with radio frequency energy harvesting (RFEH) have significant potential to improve the network throughput by utilizing vacant spectrum using battery-operated self-sustainable radio terminals. Research efforts relevant to these paradigms are focused on the mode selection policies which decide when to switch from CR mode (i.e., opportunistic vacant spectrum access mode) to the RFEH mode (i.e., battery charging using ambient RF energy) and vice-versa. So far, very little attention has been paid to the dual but competing task of frequency band selection in CR and RFEH modes under partially observable environment in the decentralized wireless networks. Furthermore, the need of tunable bandwidth frequency band access for CRs and lower subband switching cost (SSC) for energy efficient implementation have made the design of the decision making policy (DMP) more challenging. In this paper, a new CR-RFEH DMP has been proposed for RFEH enabled CR terminals in the decentralized wireless networks. The proposed DMP consists of three sub-units: 1) Bayesian approach based tunable Thompson sampling algorithm for subband statistics estimation, 2) Thompson sampling algorithm based subband access scheme exploiting the past collision events to minimize collisions among CRs, and 3) Mode selection scheme. Simulation results show that the proposed DMP offers 10–35% improvement in the throughput of the decentralized network and 40–90% reduction in the number of subband switchings compared to existing DMPs. The simulation results are then validated using real radio signals on the proposed USRP testbed.     

Hybrid crossover operators for real-coded genetic algorithms: an experimental study

Most real-coded genetic algorithm research has focused on developing effective crossover operators, and as a result, many different types have been proposed. Some forms of crossover operators are more suitable to tackle certain problems than others, even at the different stages of the genetic process in the same problem. For this reason, techniques which combine multiple crossovers have been suggested as alternative schemes to the common practice of applying only one crossover model to all the elements in the population. Therefore, the study of the synergy produced by combining the different styles of the traversal of solution space associated with the different crossover operators is an important one. The aim is to investigate whether or not the combination of crossovers perform better than the best single crossover amongst them. In this paper we have undertaken an extensive study in which we have examined the synergetic effects among real-parameter crossover operators with different search biases. This has been done by means of hybrid real-parameter crossover operators, which generate two offspring for every pair of parents, each one with a different crossover operator. Experimental results show that synergy is possible among real-parameter crossover operators, and in addition, that it is responsible for improving performance with respect to the use of a single crossover operator.     

A bit-masking oriented data structure for evolutionary operators implementation in genetic algorithms

 In the present paper a special bit-masking oriented data structure for an improved implementation of crossover and mutation operators in genetic algorithms is shown. The developed data structure performs evolutionary operators in two separate steps: crossover and mutation mask fill and a special boolean based function application. Both phases are optimized to reach a more efficient, fast and flexible genetic reproduction than standard implementations. The method has been powered adding a multi-layered, bit-masking oriented data structure and a boolean operation based control mixer, allowing special blended crossover operators obtained by superposition of the standard ones. Several examples of crossover schemes produced by these extended controls are presented. In addition, a special purpose crossover scheme, capable to process at the same time two distinct groups of design variables with separate crossover schemes is shown, in order to improve efficiency and convergence speed of some discrete/continuous optimization problems. Finally, to highlight further capabilities of the bit-masking approach, a special single-step version of an evolutionary direction operator is also illustrated.     

Localization of edges in graph models of two-level algorithms

Multidimensional computational models of two-level algorithms are introduced and investigated. Transformations of graph models of the algorithms are developed, which allow one to obtain modified models without global edges. The modified graph models can be transformed by the well-known transformation and mapping procedures into one-, two-, and three-dimensional array processors without global interconnections. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 63–71, November–December, 1999.     

Adaptive linguistic weighted aggregation operators for multi-criteria decision making

In this paper, we propose new aggregation operators for multi-criteria decision making under linguistic settings. The proposed operators are based on two sets of criteria weights. Besides the primary conventional criteria weights, we introduce a method to deduce secondary criteria weights from the criteria evaluations, which reflect the role of the different criteria in discriminating among the alternatives. The properties of the proposed operators are investigated. An approach for the application of the said operators in a group multi-criteria decision making problem is presented. Following the same, the proposed operators are applied in a case study on supplier selection. The empirical validation of the proposed operators is performed on a set of 12 real datasets.Note: All usages of he, him, his in the paper, also refer to she, and her.     

遗传算法选择方法的比较分析

本文基于改进的基本遗传算法实验,对选择方法进行了比较分析的研究,测试了四种不同选择方法：轮盘赌选择法、锦标赛选择法、随机遍历选择法以及一种新的基于种群交流的选择方法,分析比较这四种不同选择方法封种群发展及最佳适应值的影响。结果表明各种选择方法各有特点。最後为了防止陷入局部收敛,而对轮盘赌选择方法进行了改进,并比较了改进前後的结果,发现改进后的结果要好一些。     

Genetic algorithms in classifier fusion

An intense research around classifier fusion in recent years revealed that combining performance strongly depends on careful selection of classifiers to be combined. Classifier performance depends, in turn, on careful selection of features, which could be further restricted by the subspaces of the data domain. On the other hand, there is already a number of classifier fusion techniques available and the choice of the most suitable method depends back on the selections made within classifier, features and data spaces. In all these multidimensional selection tasks genetic algorithms (GA) appear to be one of the most suitable techniques providing reasonable balance between searching complexity and the performance of the solutions found. In this work, an attempt is made to revise the capability of genetic algorithms to be applied to selection across many dimensions of the classifier fusion process including data, features, classifiers and even classifier combiners. In the first of the discussed models the potential for combined classification improvement by GA-selected weights for the soft combining of classifier outputs has been investigated. The second of the proposed models describes a more general system where the specifically designed GA is applied to selection carried out simultaneously along many dimensions of the classifier fusion process. Both, the weighted soft combiners and the prototype of the three-dimensional fusion–classifier–feature selection model have been developed and tested using typical benchmark datasets and some comparative experimental results are also presented.     

A coevolutionary approach to adapt the genotype-phenotype map in genetic algorithms

This article introduces a coevolutionary approach to genetic algorithms (GAs) for exploring not only within a part of the solution space defined by the genotype-pheno-type map, but also the map itself. In canonical GAs with a fixed map, how large an area of the solution space can be covered by possible genomes, and consequently how better solutions can be found by a GA, rely on how well the geotype-phenotype map in designed, but it is difficult for designers of the algorithms to design the map without a priori knowledge of the solution space. In the proposed algorithm, the genotype-phenotype map is improved adaptively during the search process for solution candidates. It is applied to 3-bit deceptive problems such as of typical combinatorial optimazation problems. These are well known because their difficulty for GAs can be controlled by the genotype-phenotype map, and this shows a fairly good performance compared with a conventional GA. This work was presented in part at the Sixth International Symposium on Artificial Life and Robotics, Tokyo, January 15–17, 2001.     

Variational algorithms for biclustering models

Biclustering is an important tool in exploratory statistical analysis which can be used to detect latent row and column groups of different response patterns. However, few studies include covariate data directly into their biclustering models to explain these variations. A novel biclustering framework that considers both stochastic block structures and covariate effects is proposed to address this modeling problem. Fast approximation estimation algorithms are also developed to deal with a large number of latent variables and covariate coefficients. These algorithms are derived from the variational generalized expectation–maximization (EM) framework where the goal is to increase, rather than maximize, the likelihood lower bound in both E and M steps. The utility of the proposed biclustering framework is demonstrated through two block modeling applications in model-based collaborative filtering and microarray analysis.     

Adaptive reconfiguration of data networks using genetic algorithms

Genetic algorithms are applied to an important, but little investigated, network design problem, that of reconfiguring the topology and link capacities of an operational network to adapt to changes in its operating conditions. These conditions include: which nodes and links are unavailable; the traffic patterns; and the quality of service (QoS) requirements and priorities of different users and applications. Dynamic reconfiguration is possible in networks that contain links whose endpoints can be easily changed, such as satellite channels, terrestrial wireless connections, and certain types of optical connections. We report preliminary results that demonstrate the feasibility of performing genetic search quickly enough for online adaptation.     

Fuzzy adaptive genetic algorithms: design,taxonomy, and future directions

The genetic algorithm behaviour is determined by the exploitation and exploration relationship kept throughout the run. Adaptive genetic algorithms, that dynamically adjust selected control parameters or genetic operators during the evolution have been built. Their objective is to offer the most appropriate exploration and exploitation behaviour to avoid the premature convergence problem and improve the final results. One of the adaptive approaches are the adaptive parameter setting techniques based on the use of fuzzy logic controllers, the fuzzy adaptive genetic algorithms (FAGAs). In this paper, we analyse the FAGAs in depth. First, we describe the steps for their design and present an instance, which is studied from an empirical point of view. Then, we propose a taxonomy for FAGAs, attending on the combination of two aspects: the level where the adaptation takes place and the way the Rule-Bases are obtained. Furthermore, FAGAs belonging to different groups of the taxonomy are reviewed. Finally, we identify some open issues, and summarise a few new promising research directions on the topic. From the results provided by the approaches presented in the literature and the experimental results achieved in this paper, an important conclusion is obtained: the use of fuzzy logic controllers to adapt genetic algorithm parameters may really improve the genetic algorithm performance. This research has been supported by DGICYT PB98-1319.     

Machine-component grouping using genetic algorithms

One major problem in cellular manufacturing is the grouping of component parts with similar processing requirements into part families, and machines into manufacturing cells to facilitate the manufacturing of specific part families assigned to them. The objective is to minimize the total inter-cell and intra-cell movements of parts during the manufacturing process. In this paper, a mathematical model is presented to describe the characteristics of such a problem. An approach based on the concept of genetic algorithms is developed to determine the optimal machine-component groupings. Illustrative examples are used to demonstrate the efficiency of the proposed approach. Indeed, the results obtained show that the proposed genetic approach is a simple and efficient means for solving the machine-component grouping problem.     

Performance of scanline algorithms for direct display of CSG

Direct display algorithms display a CSG model without first converting the model into a boundary representation. Three such algorithms are described. All three are based on the scanline display algorithm, and are able to handle both polygonal and quadratic faces.The first algorithm is based on Atherton's recursive subdivision scanline algorithm, the second is a combination of a scanline and a ray casting algorithm, and the third is a scanline version of the Trickle algorithm. A multiprocessor system in which these algorithms can be incorporated is also described.The performances of the algorithms are compared. It turns out that the algorithms efficiently display CSG models on general-purpose architectures. A comparison is also made between the performances for polygon-approximated models and exact models for objects bounded by quadratic faces, such as spherical, cylindrical and conical faces, to get an indication of how many polygons can at most be used to approximate quadratic faces and still have better performance.     

On-line regression algorithms for learning mechanical models of robots: A survey

With the emergence of more challenging contexts for robotics, the mechanical design of robots is becoming more and more complex. Moreover, their missions often involve unforeseen physical interactions with the environment. To deal with these difficulties, endowing the controllers of the robots with the capability to learn a model of their kinematics and dynamics under changing circumstances is becoming mandatory. This emergent necessity has given rise to a significant amount of research in the Machine Learning community, generating algorithms that address more and more sophisticated on-line modeling questions. In this paper, we provide a survey of the corresponding literature with a focus on the methods rather than on the results. In particular, we provide a unified view of all recent algorithms that outlines their distinctive features and provides a framework for their combination. Finally, we give a prospective account of the evolution of the domain towards more challenging questions.     

Optimal parallel algorithms for constructing and maintaining a balancedm-way search tree

We present parallel algorithms for constructing and maintaining balancedm-way search trees. These parallel algorithms have time complexity O(1) for ann processors configuration. The formal correctness of the algorithms is given in detail.     

基于异位交叉的遗传算法的研究

针对目前遗传算法搜索速度较慢的问题，对提高遗传算法收敛速度的不同方法进行了分析。提出一种加快收敛速度的异位交叉算子，并给出算法仿其实验。仿真结果表明，这种交叉算子可比一般的对等位交叉算子更有效地提高收敛速度，且不易陷入局部最优解。具有实现简单、易于应用及鲁捧性强的特点。     

Memoryless search algorithms in a network with faulty advice

In this paper, we present a randomized algorithm for a mobile agent to search for an item stored at a node t of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I find t?” by responding with the first edge on a shortest path to t. It may happen that some nodes, called liars, give bad advice. We investigate a simple memoryless algorithm which follows the advice with some fixed probability q>1/2 and otherwise chooses a random edge. If the degree of each node and number of liars k are bounded, we show that the expected number of edges traversed by the agent before finding t is bounded from above by O(d+r^k), where d is the distance between the initial and target nodes and . We also show that this expected number of steps can be significantly improved for particular topologies such as the complete graph and the torus.     

Performance comparison of routing algorithms in wormhole-switched networks

This paper presents, building on the analytical models developed in [A. Shahrabi, M. Ould-Khoua, L. Mackenzie, Performance modelling of broadcast communication in multicomputer networks, International Journal of Parallel, Emergent, and Distributed Systems 20 (1) (2005); A. Shahrabi, M. Ould-Khoua, On the communication latency of wormhole routed interconnection networks, International Journal of Simulation 4 (5–6) (2003) 32–43; A. Shahrabi, L. Mackenzie, M. Ould-Khoua, Modelling of Adaptive Wormhole-Routed Hypercubes in the Presence of Broadcast Traffic, in: N.J. Dimopoulos, K.F. Li (Eds.), Chapter 10 in High Performance Computing Systems And Applications, Kluwer Academic Publishers, Boston, 2002; A. Shahrabi, M. Ould-Khoua, L. Mackenzie, An Analytical Model of Wormhole-Routed Hypercubes under Broadcast Traffic, Performance Evaluation 53 (1) (2003) 23–42; A. Shahrabi, M. Ould-Khoua, L. Mackenzie, Latency of double-tree broadcast in wormhole-routed hypercubes, in: Proceedings of International Conference on Parallel Processing (ICPP’01), IEEE Computer Society, 2001, pp. 401–408] a comparative performance study of adaptive and deterministic routing algorithms in wormhole-switched interconnection networks carrying a broadcast traffic component and investigates the performance vicissitudes of them under a variety of network operating conditions. In contrast to previous works, which have reported superiority of adaptive over deterministic routing especially in high-dimensional networks such as hypercubes, our results show that adaptivity does not necessarily improve network performance even for high-dimensional networks and its superiority starts to deteriorate as the broadcast fraction of generated traffic increases.