Browsing by Author "Tinos, Renato"

Now showing 1 - 14 of 14
  • No Thumbnail Available
    ItemMetadata only
    Analysis of fitness landscape modifications in evolutionary dynamic optimization
    (Elsevier, 2014-05) Tinos, Renato; Yang, Shengxiang
    In this work, discrete dynamic optimization problems (DOPs) are theoretically analysed according to the modifications produced in the fitness landscape during the optimization process. Using the proposed analysis framework, the following DOPs are analysed: problems generated by the XOR DOP generator, three versions of the dynamic 0-1 knapsack problem, one problem involving evolutionary robots in dynamic environments, and the random dynamics NK-model. The XOR DOP generator creates benchmark DOPs from any binary static optimization problem, which allows to explore the properties of the static problem in a dynamic environment. Three types of transformations occurring in the fitness landscapes are observed in the DOPs analysed here. They are caused by: i) permutation of solutions in the search space; ii) duplication of solutions; and iii) adding deviations to the fitness of a subset of solutions. The XOR DOP generator creates a special type of permutation that is not found in the other investigated DOPs. In this way, a new benchmark problem generator is proposed here based on the analysis performed, allowing to produce DOPs with six types of fitness landscape transformations, including those similar to the problems investigated in this paper. When compared to the XOR DOP generator, new algorithms can be tested and compared in a wider range of dynamic environments using the new generator. It is important to observe that some of the fitness transformations analysed here, like those caused by the duplication of solutions, are not currently explored in the evolutionary dynamic optimization area.
  • No Thumbnail Available
    ItemMetadata only
    An analysis of the XOR dynamic problem generator based on the dynamical system.
    (Springer-Verlag., 2010) Tinos, Renato; Yang, Shengxiang
    In this paper, we use the exact model (or dynamical system approach) to describe the standard evolutionary algorithm (EA) as a discrete dynamical system for dynamic optimization problems (DOPs). Based on this dynamical system model, we analyse the properties of the XOR DOP Generator, which has been widely used by researchers to create DOPs from any binary encoded problem. DOPs generated by this generator are described as DOPs with permutation, where the fitness vector is changed according to a permutation matrix. Some properties of DOPs with permutation are analyzed, which allows explaining some behaviors observed in experimental results. The analysis of the properties of problems created by the XOR DOP Generator is important to understand the results obtained in experiments with this generator and to analyze the similarity of such problems to real world DOPs.
  • No Thumbnail Available
    ItemMetadata only
    Analyzing evolutionary algorithms for dynamic optimization problems based on the dynamical system.
    (Springer-Verlag., 2013) Tinos, Renato; Yang, Shengxiang
  • Thumbnail Image
    ItemEmbargo
    Artificially inducing environmental changes in evolutionary dynamic optimization
    (Springer, 2016-08-31) Tinos, Renato; Yang, Shengxiang
    Biological and artificial evolution can be speeded up by environmental changes. From the evolutionary computation perspective, environmental changes during the optimization process generate dynamic optimization problems (DOPs). However, only DOPs caused by intrinsic changes have been investigated in the area of evolutionary dynamic optimization (EDO). This paper is devoted to investigate artificially induced DOPs. A framework to generate artificially induced DOPs from any pseudo-Boolean problem is proposed. We use this framework to induce six different types of changes in a 0–1 knapsack problem and test which one results in higher speed up. Two strategies based on immigrants, which are used in EDO, are adapted to the artificially induced DOPs investigated here. Some types of changes did not result in better performance, while some types led to higher speed up. The algorithm with memory based immigrants presented very good performance.
  • Thumbnail Image
    ItemEmbargo
    Continuous dynamic problem generators for evolutionary algorithms
    (IEEE Press, 2007) Tinos, Renato; Yang, Shengxiang
    Addressing dynamic optimization problems has attracted a growing interest from the evolutionary algorithm community in recent years due to its importance in the applications of evolutionary algorithms in real world problems. In order to study evolutionary algorithms in dynamic environments, one important work is to develop benchmark dynamic environments. This paper proposes two continuous dynamic problem generators. Both generators use linear transformation to move individuals, which preserves the distance among individuals. In the first generator, the linear transformation of individuals is equivalent to change the direction of some axes of the search space while in the second one it is obtained by successive rotations in different planes. Preliminary experiments were carried out to study the performance of some standard genetic algorithms in continuous dynamic environments created by the proposed generators.
  • No Thumbnail Available
    ItemMetadata only
    Evolution strategies with q-Gaussian mutation for dynamic optimization problems.
    (IEEE., 2010) Tinos, Renato; Yang, Shengxiang
    Evolution strategies with q-Gaussian mutation, which allows the self-adaptation of the mutation distribution shape, is proposed for dynamic optimization problems in this paper. In the proposed method, a real parameter q, which allows to smoothly control the shape of the mutation distribution, is encoded in the chromosome of the individuals and is allowed to evolve. In the experimental study, the q-Gaussian mutation is compared to Gaussian and Cauchy mutation on four experiments generated from the simulation of evolutionary robots.
  • No Thumbnail Available
    ItemMetadata only
    Evolutionary programming with q-Gaussian mutation for evolutionary optimization problems.
    (IEEE, 2008) Tinos, Renato; Yang, Shengxiang
    The use of evolutionary programming algorithms with self-adaptation of the mutation distribution for dynamic optimization problems is investigated in this paper. In the proposed method, the q-Gaussian distribution is employed to generate new candidate solutions by mutation. A real parameter q, which defines the shape of the distribution, is encoded in the chromosome of individuals and is allowed to evolve. Algorithms with self-adapted mutation generated from isotropic and anisotropic distributions are presented. In the experimental study, the q-Gaussian mutation is compared to Gaussian and Cauchy mutation on three dynamic optimization problems.
  • Thumbnail Image
    ItemOpen Access
    A framework for inducing artificial changes in optimization problems
    (Elsevier, 2019-02-14) Tinos, Renato; Yang, Shengxiang
    Environmental changes are traditionally considered intrinsic in evolutionary dynamic optimization. However, by ignoring that changes can instead be induced, we are ignoring that environmental changes can be eventually beneficial. To investigate the impact of artificial changes on the optimization speed up, we propose a framework for inducing artificial changes in any pseudo-Boolean or continuous optimization in this paper. Seven types of changes can be induced. Knowing when and how the changes occur allows us to design new strategies for evolutionary algorithms. Through computational experiments and illustrative examples, the impact of introducing changes in the optimization process is investigated. Experimental results indicate that changing the environments according to the proposed framework can lead to higher speed up, but not for all problems and change types. The best performance was obtained by change types that introduce plateaus and/or modify the gradient of regions of the fitness landscape around the current best solution. By doing this, the evolutionary dynamics is modified, eventually allowing the population to escape faster from local optima and reach new zones of the fitness landscape. Given a pseudo-Boolean or continuous optimization static problem, the proposed framework can be used to dynamically change the problem to speed up the optimization.
  • Thumbnail Image
    ItemOpen Access
    Genetic algorithms with self-organized criticality for dynamic optimization problems
    (IEEE Press, 2005) Tinos, Renato; Yang, Shengxiang
    This paper proposes a genetic algorithm (GA) with random immigrants for dynamic optimization problems where the worst individual and its neighbours are replaced every generation. In this GA, the individuals interact with each other and, when their fitness is close, as in the case where the diversity level is low, one single replacement can affect a large number of individuals. This simple approach can take the system to a kind of self-organization behavior, known as self-organized criticality (SOC), which is useful to maintain the diversity of the population in dynamic environments and hence allows the GA to escape from local optima when the problem changes. The experimental results show that the proposed GA presents the phenomenon of SOC.
  • Thumbnail Image
    ItemEmbargo
    Genetic algorithms with self-organizing behaviour in dynamic environments
    (Springer-Verlag, 2007-03) Tinos, Renato; Yang, Shengxiang
    In recent years, researchers from the genetic algorithm (GA) community have developed several approaches to enhance the performance of traditional GAs for dynamic optimization problems (DOPs). Among these approaches, one technique is to maintain the diversity of the population by inserting random immigrants into the population. This chapter investigates a self-organizing random immigrants scheme for GAs to address DOPs, where the worst individual and its next neighbours are replaced by random immigrants. In order to protect the newly introduced immigrants from being replaced by fitter individuals, they are placed in a subpopulation. In this way, individuals start to interact between themselves and, when the fitness of the individuals are close, one single replacement of an individual can affect a large number of individuals of the population in a chain reaction. The individuals in a subpopulation are not allowed to be replaced by individuals of the main population during the current chain reaction. The number of individuals in the subpopulation is given by the number of individuals created in the current chain reaction. It is important to observe that this simple approach can take the system to a self-organization behaviour, which can be useful for GAs in dynamic environments.
  • Thumbnail Image
    ItemEmbargo
    A hybrid immigrants scheme for genetic algorithms in dynamic environments
    (Springer, 2007-07-01) Tinos, Renato; Yang, Shengxiang
    Dynamic optimization problems are a kind of optimization problems that involve changes over time. They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time. Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years. Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments. One approach is to maintain the diversity of the population via random immigrants. This paper proposes a hybrid immigrants scheme that combines the concepts of elitism, dualism and random immigrants for genetic algorithms to address dynamic optimization problems. In this hybrid scheme, the best individual, i.e., the elite, from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme. These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population, replacing the worst individuals in the population. These three kinds of immigrants aim to address environmental changes of slight, medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes. Based on a series of systematically constructed dynamic test problems, experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme. Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.
  • No Thumbnail Available
    ItemMetadata only
    Hyper-selection in dynamic environments.
    (IEEE, 2008) Yang, Shengxiang; Tinos, Renato
    In recent years, several approaches have been developed for genetic algorithms to enhance their performance in dynamic environments. Among these approaches, one kind of methods is to adapt genetic operators in order for genetic algorithms to adapt to a new environment. This paper investigates the effect of the selection pressure on the performance of genetic algorithms in dynamic environments. A hyper-selection scheme is proposed for genetic algorithms, where the selection pressure is temporarily raised whenever the environment changes. The hyper-selection scheme can be combined with other approaches for genetic algorithms in dynamic environments. Experiments are carried out to investigate the effect of different selection pressures on the performance of genetic algorithms in dynamic environments and to investigate the effect of the hyper-selection scheme on the performance of genetic algorithms in combination with several other schemes in dynamic environments. The experimental results indicate that the effect of the hyper-selection scheme depends on the problem under consideration and other schemes combined in genetic algorithms.
  • Thumbnail Image
    ItemEmbargo
    Self-adaptation of mutation distribution in evolutionary algorithms
    (IEEE Press, 2007) Tinos, Renato; Yang, Shengxiang
    This paper proposes a self-adaptation method to control not only the mutation strength parameter, but also the mutation distribution for evolutionary algorithms. For this purpose, the isotropic g-Gaussian distribution is employed in the mutation operator. The g-Gaussian distribution allows to control the shape of the distribution by setting a real parameter g and can reproduce either finite second moment distributions or infinite second moment distributions. In the proposed method, the real parameter q of the g-Gaussian distribution is encoded in the chromosome of an individual and is allowed to evolve. An evolutionary programming algorithm with the proposed idea is presented. Experiments were carried out to study the performance of the proposed algorithm.
  • Thumbnail Image
    ItemEmbargo
    A self-organizing random immigrants genetic algorithm for dynamic optimization problems
    (Springer, 2007-09-01) Tinos, Renato; Yang, Shengxiang
    In this paper a genetic algorithm is proposed where the worst individual and individuals with indices close to its index are replaced in every generation by randomly generated individuals for dynamic optimization problems. In the proposed genetic algorithm, the replacement of an individual can affect other individuals in a chain reaction. The new individuals are preserved in a subpopulation which is defined by the number of individuals created in the current chain reaction. If the values of fitness are similar, as is the case with small diversity, one single replacement can affect a large number of individuals in the population. This simple approach can take the system to a self-organizing behavior, which can be useful to control the diversity level of the population and hence allows the genetic algorithm to escape from local optima once the problem changes due to the dynamics.