text: """
  Visualize Genetic Algorithm to find a path to the target.
  
  Visit my tutorial website for more: https://morvanzhou.github.io/tutorials/
  """
  import matplotlib.pyplot as plt
  import numpy as np
  
  N_MOVES = 150
  DNA_SIZE = N_MOVES*2         # 40 x moves, 40 y moves
  DIRECTION_BOUND = [0, 1]
  CROSS_RATE = 0.8
  MUTATE_RATE = 0.0001
  POP_SIZE = 100
  N_GENERATIONS = 100
  GOAL_POINT = [10, 5]
  START_POINT = [0, 5]
  OBSTACLE_LINE = np.array([[5, 2], [5, 8]])
  
  
  class GA(object):
      def __init__(self, DNA_size, DNA_bound, cross_rate, mutation_rate, pop_size, ):
          self.DNA_size = DNA_size
          DNA_bound[1] += 1
          self.DNA_bound = DNA_bound
          self.cross_rate = cross_rate
          self.mutate_rate = mutation_rate
          self.pop_size = pop_size
  
          self.pop = np.random.randint(*DNA_bound, size=(pop_size, DNA_size))
  
      def DNA2product(self, DNA, n_moves, start_point):                 # convert to readable string
          pop = (DNA - 0.5) / 2
          pop[:, 0], pop[:, n_moves] = start_point[0], start_point[1]
          lines_x = np.cumsum(pop[:, :n_moves], axis=1)
          lines_y = np.cumsum(pop[:, n_moves:], axis=1)
          return lines_x, lines_y
  
      def get_fitness(self, lines_x, lines_y, goal_point, obstacle_line):
          dist2goal = np.sqrt((goal_point[0] - lines_x[:, -1]) ** 2 + (goal_point[1] - lines_y[:, -1]) ** 2)
          fitness = np.power(1 / (dist2goal + 1), 2)
          points = (lines_x > obstacle_line[0, 0] - 0.5) & (lines_x < obstacle_line[1, 0] + 0.5)
          y_values = np.where(points, lines_y, np.zeros_like(lines_y) - 100)
          bad_lines = ((y_values > obstacle_line[0, 1]) & (y_values < obstacle_line[1, 1])).max(axis=1)
          fitness[bad_lines] = 1e-6
          return fitness
  
      def select(self, fitness):
          idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True, p=fitness/fitness.sum())
          return self.pop[idx]
  
      def crossover(self, parent, pop):
          if np.random.rand() < self.cross_rate:
              i_ = np.random.randint(0, self.pop_size, size=1)  # select another individual from pop
              cross_points = np.random.randint(0, 2, self.DNA_size).astype(np.bool)   # choose crossover points
              parent[cross_points] = pop[i_, cross_points]                            # mating and produce one child
          return parent
  
      def mutate(self, child):
          for point in range(self.DNA_size):
              if np.random.rand() < self.mutate_rate:
                  child[point] = np.random.randint(*self.DNA_bound)
          return child
  
      def evolve(self, fitness):
          pop = self.select(fitness)
          pop_copy = pop.copy()
          for parent in pop:  # for every parent
              child = self.crossover(parent, pop_copy)
              child = self.mutate(child)
              parent[:] = child
          self.pop = pop
  
  
  class Line(object):
      def __init__(self, n_moves, goal_point, start_point, obstacle_line):
          self.n_moves = n_moves
          self.goal_point = goal_point
          self.start_point = start_point
          self.obstacle_line = obstacle_line
  
          plt.ion()
  
      def plotting(self, lines_x, lines_y):
          plt.cla()
          plt.scatter(*self.goal_point, s=200, c='r')
          plt.scatter(*self.start_point, s=100, c='b')
          plt.plot(self.obstacle_line[:, 0], self.obstacle_line[:, 1], lw=3, c='k')
          plt.plot(lines_x.T, lines_y.T, c='k')
          plt.xlim((-5, 15))
          plt.ylim((-5, 15))
          plt.pause(0.01)
  
  
  ga = GA(DNA_size=DNA_SIZE, DNA_bound=DIRECTION_BOUND,
          cross_rate=CROSS_RATE, mutation_rate=MUTATE_RATE, pop_size=POP_SIZE)
  
  env = Line(N_MOVES, GOAL_POINT, START_POINT, OBSTACLE_LINE)
  
  for generation in range(N_GENERATIONS):
      lx, ly = ga.DNA2product(ga.pop, N_MOVES, START_POINT)
      fitness = ga.get_fitness(lx, ly, GOAL_POINT, OBSTACLE_LINE)
      ga.evolve(fitness)
      print('Gen:', generation, '| best fit:', fitness.max())
      env.plotting(lx, ly)
  
  plt.ioff()
  plt.show()
  
  
  