Scheduling tasks of a parallel program in two-processor systems with use of cellular automata

In this paper, a cellular automaton (CA) is proposed as a tool for designing distributed scheduling algorithms for allocating parallel program tasks in multiprocessor systems. For this purpose, a program graph is considered as a CA containing elementary automata interacting locally according to some rules. In the first phase of the algorithm, effective rules for the CA are discovered by a genetic algorithm. In the second phase, the CA works as a distributed scheduler. In this phase, for any initial allocation of tasks in a multiprocessor system, the CA-based scheduler finds an allocation minimizing the total execution time of the program in a given system topology. The effectiveness of the proposed scheduling algorithm is shown for a number of program graphs scheduled in a two-processor system.     

Garden of eden configurations for 2-D cellular automata with rule 2460 N

An important problem in cellular automata theory is the reversibility of a cellular automaton which is related to the existence of Garden of Eden configurations in cellular automata. In this paper, we study new local rules for two-dimensional cellular automata over the ternary field Z₃ (the set of integers modulo three) with some of their important characteristics. We obtain necessary and sufficient conditions for the existence of Garden of Eden configurations for two-dimensional ternary cellular automata. Also by making use of the matrix representation of two-dimensional cellular automata, we provide an algorithm to obtain the number of Garden of Eden configurations for two-dimensional cellular automata defined by rule 2460 N. We present an application of the reversible two-dimensional ternary cellular automata to cryptography.     

Rough milling optimisation for parts with sculptured surfaces using genetic algorithms in a Stackelberg game

In rough milling of sculptured surface parts, decisions on process parameters concern feedrate, spindle speed, cutting speed, width of cut, raster pattern angle and number of machining slices of variable thickness. In this paper three rough milling objectives are considered: minimum machining time, maximum removed material and maximum uniformity of the remaining volume at the end of roughing. Owing to the complexity of the modelled problem and the large number of parameters, typical genetic algorithms cannot achieve global optima without defining case-dependent constraints. Therefore, to achieve generality, a hierarchical game similar to a Stackelberg game is implemented in which a typical Genetic Algorithm functions as the leader and micro-Genetic Algorithms as followers. In this game, one of the leader’s parameters is responsible for creating a follower’s population and for triggering the optimisation. After properly weighing the three objectives, the follower performs single-objective optimization in steps and feeds the leader back with the objective values as they appear prior to weighing. Micro-Genetic Algorithm (follower) chromosome consists of the distribution of machining slice thickness, while the typical Genetic Algorithm (leader) consists of the milling parameters. The methodology is tested on sculptured surface parts with different properties, and a representative case is presented here.     

Identifying dominant factors for the calibration of a land-use cellular automata model using Rough Set Theory

While cellular automata (CA) are increasingly used for modeling urban growth and land-use changes, the methods for identifying the dominant factors that drive the landscape dynamics when calibrating the model still require improvement, specifically in the context where a large number of factors are considered. In this paper, the potential of Rough Set Theory (RST) to guide the factor selection is evaluated. This data mining approach was tested for the calibration of a CA model to simulate land-use changes in a portion of the Elbow River watershed adjacent to the City of Calgary, in southern Alberta, Canada. Simulation outcomes obtained using a total of 18 original factors and a smaller set of factors identified with RST were compared to reference land-use maps using three Kappa coefficients of agreement. Results reveal that the factors selected by RST are not identical for each land use. Among the identified factors, three external factors (distance to river, distance to Calgary City center, and distance to road) and the presence of Built-up areas in the three considered neighborhoods are the most important factors driving the transition from Forest and Vegetation (including agriculture and Rangeland/Parkland) to Built-up. The Kappa statistics reveal that the factors selected by RST tend to generate a higher agreement with reference land-use maps than the original group of 18 factors and that they are better at capturing quantity information than location information. An advantage of RST is that it retains the original factors in the identification of the transition rules. In addition, the computation time required for the simulation using the RST factors is considerably less than the time needed to generate the results using the original set of factors. However, the data mining technique itself is computationally intensive. This study illustrates that RST can guide the selection of the dominant factors required in the calibration of a CA model, but that its potential still needs to be further investigated.     

Multi-criteria genetic optimisation of the manoeuvres of a two-stage launcher

The aim of this paper is to study the use of a genetic algorithm (GA) to optimise the ascent trajectory of a conventional two-stage launcher. The equations of motion of this system lack analytical solutions, and the number of adjustable parameters is large enough that the use of some non-traditional optimisation method becomes necessary. Two different missions are considered: first, to reach the highest possible stable, circular Low Earth Orbit (LEO); and second, to maximise the speed of a tangential escape trajectory. In this study, three variables are tuned and optimised by the GA in order to satisfy mission constraints while maximising the target function. The technical characteristics and limitations of the launcher are taken into account in the mission model, and a fixed payload weight is assumed. A variable mutation rate helps expand the search area whenever the population of solutions becomes uniform, and is shown to accelerate convergence of the GA in both cases. The obtained results are in agreement with technical specifications and solutions obtained in the past.     

Self-adjusting the intensity of assortative mating in genetic algorithms

Mate selection plays a crucial role in both natural and artificial systems. While traditional Evolutionary Algorithms (EA) usually engage in random mating strategies, that is, mating chance is independent of genotypic or phenotypic distance between individuals, in natural systems non-random mating is common, which means that somehow this mechanism has been favored during the evolutionary process. In non-random mating, the individuals mate according to their parenthood or likeness. Previous studies indicate that negative assortative mating (AM)—also known as dissortative mating—, which is a specific type of non-random mating, may improve EAs performance by maintaining the genetic diversity of the population at a higher level during the search process. In this paper we present the Variable Dissortative Mating Genetic Algorithm (VDMGA). The algorithm holds a mechanism that varies the GA’s mating restrictions during the run by means of simple rule based on the number of chromosomes created in each generation and indirectly influenced by the genetic diversity of the population. We compare VDMGA not only with traditional Genetic Algorithms (GA) but also with two preceding non-random mating EAs: the CHC algorithm and the negative Assortative Mating Genetic Algorithm (nAMGA). We intend to study the effects of the different methods in the performance of GAs and verify the reliability of the proposed algorithm when facing an heterogeneous set of landscapes. In addition, we include the positive Assortative Mating Genetic Algorithm (pAMGA) in the experiments in order test both negative and positive AM mechanisms, and try to understand if and when negative AM (or DM) speeds up the search process or enables the GAs to escape local optima traps. For these purposes, an extensive set of optimization test problems was chosen to cover a variety of search landscapes with different characteristics. Our results confirm that negative AM is effective in leading EAs out of local optima traps, and show that the proposed VDMGA is at least as efficient as nAMGA when applied to the range of our problems, being more efficient in very hard functions were traditional GAs usually fail to escape local optima. Also, scalability tests have been made that show VDMGA ability to decrease optimal population size, thus reducing the amount of evaluations needed to attain global optima. We like to stress that only two parameters need to be hand-tuned in VDMGA, thus reducing the tuning effort present in traditional GAs and nAMGA.     

Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem

In this paper we perform extensive computational experiments solving quadratic assignment problems using various variants of a hybrid genetic algorithm. We introduce a new tabu search (simple tabu). We compared the modified robust tabu and the simple tabu as improvement algorithms in a hybrid genetic algorithm with other tabu searches (concentric tabu, ring moves, all moves, robust tabu) with superior results. We also tested several modifications of the hybrid genetic algorithm and all of them produced good results.     

Designing feedforward command shapers with multi-objective genetic optimisation for vibration control of a single-link flexible manipulator

This paper presents investigations into the design of a command-shaping technique using multi-objective genetic optimisation process for vibration control of a single-link flexible manipulator. Conventional design of a command shaper requires a priori knowledge of natural frequencies and associated damping ratios of the system, which may not be available for complex flexible systems. Moreover, command shaping in principle causes delay in system's response while it reduces system vibration and in this manner the amount of vibration reduction and the rise time conflict one another. Furthermore, system performance objectives, such as, reduced overshoot, rise time, settling time, and end-point vibration are found in conflict with one another due to the construction and mode of operation of a flexible manipulator. Conventional methods can hardly provide a solution, for a designer-oriented formulation, satisfying several objectives and associated goals as demanded by a practical application due to the competing nature of those objectives. In such cases, multi-objective optimisation can provide a wide range of solutions, which trade-off these conflicting objectives so as to satisfy associated goals. A multi-modal command shaper consists of impulses of different amplitudes at different time locations, which are convolved with one another and then with the desired reference and then used as reference (for closed loop) or applied to system (for open loop) with the view to reduce vibration of the system, mainly at dominant modes. Multi-objective optimisation technique is used to determine a set of solutions for the amplitudes and corresponding time locations of impulses of a multi-modal command shaper. The effectiveness of the proposed technique is assessed both in the time domain and the frequency domain. Moreover, a comparative assessment of the performance of the technique with the system response with unshaped bang–bang input is presented.     

A review of the current applications of genetic algorithms in assembly line balancing

Most of the problems involving the design and plan of manufacturing systems are combinatorial and NP-hard. A well-known manufacturing optimization problem is the assembly line balancing problem (ALBP). Due to the complexity of the problem, in recent years, a growing number of researchers have employed genetic algorithms. In this article, a survey has been conducted from the recent published literature on assembly line balancing including genetic algorithms. In particular, we have summarized the main specifications of the problems studied, the genetic algorithms suggested and the objective functions used in evaluating the performance of the genetic algorithms. Moreover, future research directions have been identified and are suggested.     

Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms

Organising shifts, or work rosters, is a problem that affects a large number of businesses where employees are subject to some kind of work rotation. Researchers in the fields of Operations Research and Artificial Intelligence have resorted to several different optimisation systems to solve the problem. The motivation for the medical-staff shift-rotation research presented in this paper stems from the needs of an actual hospital emergency department (HED) and from the observed growing staff of these services in Spain. The problem approach, which has been hardly dealt with in the literature, intends to automate the creation of time-tables by applying genetic algorithms (GAs) in an actual HED. HEDs work organisation becomes different because of the combination of shifts and 24-h duties. After knowing the HED workers’ requirements (which will allow to identify the hard and soft constraints imposed to the problem) and after defining the adequate encoding to be used in the solutions, a heuristic-schedule builder –designed ad hoc to satisfy the hard constraints – produces an initial population of feasible solutions. Afterwards, iteratively, GA obtains new generations of feasible individuals, thanks to the use of a specific crossover operator, based in the exchange of whole work weeks, that operates together with a repair function. Once the optimum is reached, the results obtained are discussed as a function of the degree of satisfaction of the constraints under which the system operates and of the adaptability of the system as the constraints vary.     

Optimization of interval type-2 fuzzy logic controllers for a perturbed autonomous wheeled mobile robot using genetic algorithms

We describe a tracking controller for the dynamic model of a unicycle mobile robot by integrating a kinematic and a torque controller based on type-2 fuzzy logic theory and genetic algorithms. Computer simulations are presented confirming the performance of the tracking controller and its application to different navigation problems.     

A new efficient encoding/decoding procedure for the design of a supply chain network with genetic algorithms

Supply chain network (SCN) design is a strategic issue which aims at selecting the best combination of a set of facilities to achieve an efficient and effective management of the supply chain. This paper presents an innovative encoding–decoding procedure embedded within a genetic algorithm (GA) to minimize the total logistic cost resulting from the transportation of goods and the location and opening of the facilities in a single product three-stage supply chain network. The new procedure allows a proper demand allocation procedure to be run which avoids the decoding of unfeasible distribution flows at the stage of the supply chain transporting products from plants to distribution centers. A numerical study on a benchmark of problems demonstrates the statistical outperformance of the proposed approach vs. others currently available in literature in terms of total supply chain logistic cost saving and reduction of the required computation burden to achieve an optimal design.     

An optimization method for designing type-2 fuzzy inference systems based on the footprint of uncertainty using genetic algorithms

This paper proposes an optimization method for designing type-2 fuzzy inference systems based on the footprint of uncertainty (FOU) of the membership functions, considering three different cases to reduce the complexity problem of searching the parameter space of solutions. For the optimization method, we propose the use of a genetic algorithm (GA) to optimize the type-2 fuzzy inference systems, considering different cases for changing the level of uncertainty of the membership functions to reach the optimal solution at the end.     

The application of genetic algorithms to optimise the performance of a mine ventilation network: the influence of coding method and population size

This paper presents an application of genetic algorithms (GAs) to the solution of a real-world optimisation problem. The proposed GA method investigates the optimisation of a mine ventilation system to minimise the operational fan power costs by the determination of the most effective combination of the fan operational duties and locations. The paper examines the influence that both the encoding method and the population size have on the performance of the GA. The relative performance of the GA produced by the use of two different encoding methods (a binary and a hybrid code) and various solution population sizes is assessed by performing a two way ANOVA analysis. It is concluded that the genetic algorithm approach offers both an effective and efficient optimisation method in the selection and evaluation of the cost-effective solutions in the planning and operation of mine ventilation systems.     

Modeling the expectations of inflation in the OLG model with genetic programming

 In this paper, genetic programming (GP) is employed to model learning and adaptation in the overlapping generations model, one of the most popular dynamic economic models. Using a model of inflation with multiple equilibria as an illustrative example, we show that our GP-based agents are able to coordinate their actions to achieve the Pareto-superior equilibrium (the low-inflation steady state) rather than the Pareto inferior equilibrium (the high-inflation steady state). We also test the robustness of this result with different initial conditions, economic parameters, GP control parameters, and the selection mechanism. We find that as long as the survival-of-the-fittest principle is maintained, the evolutionary operators are only secondarily important. However, once the survival-of-the-fittest principle is absent, the well-coordinated economy is also gone and the inflation rate can jump quite wildly. To some extent, these results shed light on the biological foundations of economics.     

The design of a fuzzy cascade controller for ball and beam system: A study in optimization with the use of parallel genetic algorithms

In this study, we introduce a design methodology for an optimized fuzzy cascade controller for ball and beam system by exploiting the use of hierarchical fair competition-based genetic algorithm (HFCGA). The ball and beam system is a well-known control engineering experimental setup which consists of servo motor, beam and ball and exhibits a number of interesting and challenging properties when considered from the control perspective. The position of ball is determined through the control of a servo motor. The displacement change of the position of ball requires the change of the angle of the beam which determines the position angle of a servo motor. Consequently, the variation of the position of the moving ball and the ensuing change of the angle of the beam results in the change of the position angle of a servo motor. We introduce the fuzzy cascade controller scheme which consists of the outer (1st) controller and the inner (2nd) controller in a cascaded architecture. Auto-tuning of the parameters of the controller (viz. scaling factors) of each fuzzy controller is realized with the use of the HFCGA. The set-point value of the inner controller (the 2nd controller) corresponds to the position angle of a servo motor, and is given as a reference value which enters into the inner controller as the 2nd controller of the two cascaded controllers. HFCGA is a kind of a parallel genetic algorithm (PGA), which helps alleviate an effect of premature convergence being a potential shortcoming present in conventional genetic algorithms (GAs). A detailed comparative analysis carried out from the viewpoint of the performance and the design methodology, is provided for the fuzzy cascade controller and the conventional PD cascade controller whose design relied on the use of the serial genetic algorithms.     

Forecasting the NYSE composite index with technical analysis, pattern recognizer, neural network, and genetic algorithm: a case study in romantic decision support

The 21st century is seeing technological advances that make it possible to build more robust and sophisticated decision support systems than ever before. But the effectiveness of these systems may be limited if we do not consider more eclectic (or romantic) options. This paper exemplifies the potential that lies in the novel application and combination of methods, in this case to evaluating stock market purchasing opportunities using the “technical analysis” school of stock market prediction. Members of the technical analysis school predict market prices and movements based on the dynamics of market price and volume, rather than on economic fundamentals such as earnings and market share. The results of this paper support the effectiveness of the technical analysis approach through use of the “bull flag” price and volume pattern heuristic. The romantic approach to decision support exemplified in this paper is made possible by the recent development of: (1) high-performance desktop computing, (2) the methods and techniques of machine learning and soft computing, including neural networks and genetic algorithms, and (3) approaches recently developed that combine diverse classification and forecasting systems. The contribution of this paper lies in the novel application and combination of the decision-making methods and in the nature and superior quality of the results achieved.     

Study of the Radio Frequency (RF) performance of a Wafer-Level Package (WLP) with Through Silicon Vias (TSVs) for the integration of RF-MEMS and micromachined waveguides in the context of 5G and Internet of Things (IoT) applications. Part 2: parameterised 3D model and optimisation

Microsystem Technologies - This study discusses the exploitation of a full-3D methodology for the electromagnetic simulation of a Wafer-Level Packaging solution featuring Through Silicon Vias...