Graph structure optimization of Genetic Network Programming with ant colony mechanism in deterministic and stochastic environments

Abstract Evolutionary Algorithms are of the most successful algorithms in solving various optimization problems. Genetic network programming is one of the Evolutionary Algorithms with good capabilities in agent control problems. In this algorithm, the individuals’ structure is a directed graph. Using this structure, it is possible to model the solution of many complex problems. However, in this algorithm, crossover and mutation operators repeatedly break the structures of individuals and make new ones. Although this can lead to better structures, it may break suitable structures in elite individuals. Meanwhile, in stochastic environments, each time an individual is evaluated, it leads to different fitness values. So, calculating the fitness value of individuals requires evaluating each individual several times. This extremely decreases the evolution process speed. In this paper, inspired by mechanisms of ant colony algorithm, a new method is proposed to prevent the algorithm from iteratively breaking down the structures of individuals. This method improves the performance of individuals from one generation to the next using a constructive process. Unlike generative process that the individuals are generated by combination of some others, in constructive process they are produced according to the experience of previous generations. Using this mechanism, we not only prevent breaking suitable structures but also can manage uncertainty in stochastic environments. Our proposed method is used to solve two agent control problems when the environment is deterministic or stochastic. The results show that the proposed algorithm has very high ability in creating an efficient decision making strategies especially in stochastic environments.