Evolution of lace knitting stitch patterns by genetic programming

In this paper we study the generation of lace knitting stitch patterns by using genetic programming. We devise a genetic representation of knitting charts that accurately reflects their usage for hand knitting the pattern. We apply a basic evolutionary algorithm for generating the patterns, where the key of success is evaluation. We propose automatic evaluation of the patterns, without interaction with the user. We present some patterns generated by the method and then discuss further possibilities for bringing automatic evaluation closer to human evaluation. Copyright 2007 ACM.

To be(long) or not to be(long):social identification in organizational contexts

In the past few years, ideas of Social Identity Theory and Self-Categorization Theory have been successfully applied to the organizational domain. In this article, the authors provide an overview of these recent developments and present a concept of social identification in organizational contexts, based on these theories. The assumptions of this framework are that (a) social identification in organizational contexts is a multifaceted concept consisting of different dimensions and foci (or targets), (b) higher levels of identification are related to higher productivity and more positive work-related attitudes, and (c) identification is a very flexible concept that is linked to the situational context. The authors present the results of a series of field and laboratory studies in which the proposed relationships are analyzed and, in the main, confirmed. Copyright © 2006 Heldref Publications.

Temperature management for heterogeneous multi-core FPGAs using adaptive evolutionary multi-objective approaches

Heterogeneous multi-core FPGAs contain different types of cores, which can improve efficiency when used with an effective online task scheduler. However, it is not easy to find the right cores for tasks when there are multiple objectives or dozens of cores. Inappropriate scheduling may cause hot spots which decrease the reliability of the chip. Given that, our research builds a simulating platform to evaluate all kinds of scheduling algorithms on a variety of architectures. On this platform, we provide an online scheduler which uses multi-objective evolutionary algorithm (EA). Comparing the EA and current algorithms such as Predictive Dynamic Thermal Management (PDTM) and Adaptive Temperature Threshold Dynamic Thermal Management (ATDTM), we find some drawbacks in previous work. First, current algorithms are overly dependent on manually set constant parameters. Second, those algorithms neglect optimization for heterogeneous architectures. Third, they use single-objective methods, or use linear weighting method to convert a multi-objective optimization into a single-objective optimization. Unlike other algorithms, the EA is adaptive and does not require resetting parameters when workloads switch from one to another. EAs also improve performance when used on heterogeneous architecture. A efficient Pareto front can be obtained with EAs for the purpose of multiple objectives.

Evolution of competing strategies in a threshold model for task allocation

A nature inspired decentralised multi-agent algorithm is proposed to solve a problem of distributed task allocation in which cities produce and store batches of different mail types. Agents must collect and process the mail batches, without global knowledge of their environment or communication between agents. The problem is constrained so that agents are penalised for switching mail types. When an agent process a mail batch of different type to the previous one, it must undergo a change-over, with repeated change-overs rendering the agent inactive. The efficiency (average amount of mail retrieved), and the flexibility (ability of the agents to react to changes in the environment) are investigated both in static and dynamic environments and with respect to sudden changes. New rules for mail selection and specialisation are proposed and are shown to exhibit improved efficiency and flexibility compared to existing ones. We employ a evolutionary algorithm which allows the various rules to evolve and compete. Apart from obtaining optimised parameters for the various rules for any environment, we also observe extinction and speciation.

Operation sequencing optimization for five-axis prismatic parts using a particle swarm optimization approach

Operation sequencing is one of the crucial tasks in process planning. However, it is an intractable process to identify an optimized operation sequence with minimal machining cost in a vast search space constrained by manufacturing conditions. Also, the information represented by current process plan models for three-axis machining is not sufficient for five-axis machining owing to the two extra degrees of freedom and the difficulty of set-up planning. In this paper, a representation of process plans for five-axis machining is proposed, and the complicated operation sequencing process is modelled as a combinatorial optimization problem. A modern evolutionary algorithm, i.e. the particle swarm optimization (PSO) algorithm, has been employed and modified to solve it effectively. Initial process plan solutions are formed and encoded into particles of the PSO algorithm. The particles 'fly' intelligently in the search space to achieve the best sequence according to the optimization strategies of the PSO algorithm. Meanwhile, to explore the search space comprehensively and to avoid being trapped into local optima, several new operators have been developed to improve the particle movements to form a modified PSO algorithm. A case study used to verify the performance of the modified PSO algorithm shows that the developed PSO can generate satisfactory results in optimizing the process planning problem. © IMechE 2009.

Towards identifying salient patterns in genetic programming individuals

This thesis addresses the problem of offline identification of salient patterns in genetic programming individuals. It discusses the main issues related to automatic pattern identification systems, namely that these (a) should help in understanding the final solutions of the evolutionary run, (b) should give insight into the course of evolution and (c) should be helpful in optimizing future runs. Moreover, it proposes an algorithm, Extended Pattern Growing Algorithm ([E]PGA) to extract, filter and sort the identified patterns so that these fulfill as many as possible of the following criteria: (a) they are representative for the evolutionary run and/or search space, (b) they are human-friendly and (c) their numbers are within reasonable limits. The results are demonstrated on six problems from different domains.

Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop

The re-entrant flow shop scheduling problem (RFSP) is regarded as a NP-hard problem and attracted the attention of both researchers and industry. Current approach attempts to minimize the makespan of RFSP without considering the interdependency between the resource constraints and the re-entrant probability. This paper proposed Multi-level genetic algorithm (GA) by including the co-related re-entrant possibility and production mode in multi-level chromosome encoding. Repair operator is incorporated in the Multi-level genetic algorithm so as to revise the infeasible solution by resolving the resource conflict. With the objective of minimizing the makespan, Multi-level genetic algorithm (GA) is proposed and ANOVA is used to fine tune the parameter setting of GA. The experiment shows that the proposed approach is more effective to find the near-optimal schedule than the simulated annealing algorithm for both small-size problem and large-size problem. © 2013 Published by Elsevier Ltd.

The dynamics of a genetic algorithm for a simple learning problem

A formalism for describing the dynamics of Genetic Algorithms (GAs) using method s from statistical mechanics is applied to the problem of generalization in a perceptron with binary weights. The dynamics are solved for the case where a new batch of training patterns is presented to each population member each generation, which considerably simplifies the calculation. The theory is shown to agree closely to simulations of a real GA averaged over many runs, accurately predicting the mean best solution found. For weak selection and large problem size the difference equations describing the dynamics can be expressed analytically and we find that the effects of noise due to the finite size of each training batch can be removed by increasing the population size appropriately. If this population resizing is used, one can deduce the most computationally efficient size of training batch each generation. For independent patterns this choice also gives the minimum total number of training patterns used. Although using independent patterns is a very inefficient use of training patterns in general, this work may also prove useful for determining the optimum batch size in the case where patterns are recycled.

The dynamics of a genetic algorithm under stabilizing selection

A formalism recently introduced by Prugel-Bennett and Shapiro uses the methods of statistical mechanics to model the dynamics of genetic algorithms. To be of more general interest than the test cases they consider. In this paper, the technique is applied to the subset sum problem, which is a combinatorial optimization problem with a strongly non-linear energy (fitness) function and many local minima under single spin flip dynamics. It is a problem which exhibits an interesting dynamics, reminiscent of stabilizing selection in population biology. The dynamics are solved under certain simplifying assumptions and are reduced to a set of difference equations for a small number of relevant quantities. The quantities used are the population's cumulants, which describe its shape, and the mean correlation within the population, which measures the microscopic similarity of population members. Including the mean correlation allows a better description of the population than the cumulants alone would provide and represents a new and important extension of the technique. The formalism includes finite population effects and describes problems of realistic size. The theory is shown to agree closely to simulations of a real genetic algorithm and the mean best energy is accurately predicted.

Identification of residues controlling transport through the yeast aquaglyceroporin Fps1 using a genetic screen

Aquaporins and aquaglyceroporins mediate the transport of water and solutes across biological membranes. Saccharomyces cerevisiae Fps1 is an aquaglyceroporin that mediates controlled glycerol export during osmoregulation. The transport function of Fps1 is rapidly regulated by osmotic changes in an apparently unique way and distinct regions within the long N- and C-terminal extensions are needed for this regulation. In order to learn more about the mechanisms that control Fps1 we have set up a genetic screen for hyperactive Fps1 and isolated mutations in 14 distinct residues, all facing the inside of the cell. Five of the residues lie within the previously characterized N-terminal regulatory domain and two mutations are located within the approach to the first transmembrane domain. Three mutations cause truncation of the C-terminus, confirming previous studies on the importance of this region for channel control. Furthermore, the novel mutations identify two conserved residues in the channel-forming B-loop as critical for channel control. Structural modelling-based rationalization of the observed mutations supports the notion that the N-terminal regulatory domain and the B-loop could interact in channel control. Our findings provide a framework for further genetic and structural analysis to better understand the mechanism that controls Fps1 function by osmotic changes.

A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.