Works‎ > ‎

Genetic Algorithm with Social Interaction N-People (NpSIGA)

Abstract: This paper presents an extensive study on Genetic Algorithm with game teory for N-person, thereby, there is an increase in the variability of the population and decreases the probability of the algorithm to stall in an optimal location. Individuals of the population have two chromosomes, as follows: one for solution of the problem, in this case, instances of Traveling Salesman Problem (TSP); and another for the genetic coding of behavior, this is necessary to define the strategy used by them, during the disputes of the games. For the experiments, the implementation process was defined and constructed chronologically: Implementation of the classic genetic algorithm (GA); Combinação do AG com a fase de interação social (SIGA); use of the Prisoner's Dilemma Paradigm Classic (2-people); Application of the concept of N-people, where individuals have a tolerance rate of betrayal. In addition, we also implemented the features: in each generation, the population is composed of unique individuals; elitism; the possibility of parents selected for crossover does not generate offspring; and after, they can mutate; mutation with a memory which may or may not occur. Finally, we performed 16 tests for the instance of BR-26, which defines the distance between all Brazilian capitals connected by roads. The results demonstrate the feasibility of the methodology, and also point to many other application possibilities and expansion.

Keywords: NpSIGA, Evolutionary Computation, Genetic Algorithms, Game Theory N-Players, Paradigm of the Prisoner's Dilemma.

Author (s): Lilian de Jesus Chaves Dias, Pedro Victor Pontes Pinheiro, Roberto Yuri da Silva Franco.