Typescript での遺伝的アルゴリズムの実装例

Typescript での遺伝的アルゴリズムの実装例

Typescript での遺伝的アルゴリズムの実装例です。
・個体クラス: BaseIndividual
・GAクラス: BaseGeneticAlgorithm
これらのライブラリを継承して、巡回セールスマン問題に適用してみます。

■遺伝的アルゴリズムのライブラリ（BaseGeneticAlgorithm）

/**
 *
 * Base Genentic Algorithms
 *
 */
/**
 * config
 * timeout_msec: Number    # timeout in msec
 * max_population: Number  #
 * fitness_min: Boolean    # true: asc, false: desc
 * max_population: Number  # 
 * 
 */


export class BaseIndividual {
  public fitness: number | null;
  public genes: any | null;
  public encoded: string | null;
  
  
  public constructor() {
  }

  
  public encode(): string | null {
    this.encoded = null;
    return this.encoded;
  }
}



export class BaseGeneticAlgorithm {
  public config: any;
  public population: Array<BaseIndividual> = [];
  public fitness_map = {};

  
  public constructor(config: any) {
    this.config = config;
  }


  public add_population(new_pop: Array<BaseIndividual>) {
    for (let ind of new_pop) {
      ind.encode();
      this.fitness(ind);
      this.population.push(ind);
    }
  }

  
  public select1() {
    const i = Math.floor(Math.random() * this.population.length);
    return this.population[i];
  }


  public select2() {
    const i = Math.floor(Math.random() * this.population.length);
    let j = Math.floor(Math.random() * this.population.length);
    if (i == j) j = (j + i) % this.population.length;
    return [this.population[i], this.population[j]];
  }
  
  
  public fitness(ind: BaseIndividual): number {
    return 0;
  }
  
  
  public crossover(ind1: BaseIndividual, ind2: BaseIndividual):
  Array<BaseIndividual> {
    const new_ind1 = new BaseIndividual()
    new_ind1.encode();
    this.fitness(new_ind1);
    
    const new_ind2 = new BaseIndividual();
    new_ind2.encode();
    this.fitness(new_ind2);
    
    return [new_ind1, new_ind2];
  }
  
  
  public mutate(ind: BaseIndividual): BaseIndividual {
    const new_ind = new BaseIndividual();
    this.fitness(new_ind);
    new_ind.encode();
    return new_ind;
  }


  public append(new_pop: Array<BaseIndividual>, new_pop_map: any, ind: BaseIndividual) {
    if (ind.encoded === null) {
      new_pop.push(ind);
      return true;
    }
    
    if (ind.encoded in new_pop_map) return false;

    new_pop.push(ind);
    new_pop_map[ind.encoded] = true;
    return true;
  }
  
  
  public evolve1() {
    const c = this.config
    const pop = this.population;
    const pop_map = {};
    let new_pop = [];

    for (let ind of pop) {
      if (ind.encoded === null) continue;
      pop_map[ind.encoded] = true;
    }
    
    // crossover
    const num_crossover = c.max_population * c.rate_num_crossover;
    for (let i = 0; i < num_crossover; i++) {
      let inds = this.select2();
      let new_inds = this.crossover(inds[0], inds[1]);
      this.append(new_pop, pop_map, new_inds[0]);
      this.append(new_pop, pop_map, new_inds[1]);
    }
    
    // mutate
    const num_mutate = c.max_population * c.rate_num_mutate;
    for (let i = 0; i < num_mutate; i++) {
      let ind = this.select1();
      let new_ind = this.mutate(ind);
      this.append(new_pop, pop_map, new_ind);
    }
    
    // fitness
    new_pop = new_pop.concat(pop);
    if (c.fitness_order_by_asc) {
      new_pop = new_pop.sort((a, b) => {
	if (a.fitness < b.fitness) return -1;
	else if (a.fitness > b.fitness) return 1;
	else return 0;
      });
    }
    else {
      //console.log(`order: desc`);
      new_pop = new_pop.sort((a, b) => {
	if (a.fitness > b.fitness) return -1;
	else if (a.fitness < b.fitness) return 1;
	else return 0;
      });
    }
    new_pop = new_pop.slice(0, c.max_population);
    this.population = new_pop;
  }
  
  
  public evolve() {
    const c = this.config;
    const start_time = (new Date()).getTime();

    for (let i = 0; i < c.max_iteration; i++) {
      this.evolve1();
      let cur_time = (new Date()).getTime();
      if (cur_time - start_time > c.timeout_msec) break;
    }
  }
}

■巡回セールスマン問題への適用（tsp1.ts）

/**
 *
 * Travelling Salesman Problem
 *
 * 遺伝子は未訪問の都市
 * genes[0]: 1番目の都市のインデックス（0 ～ N-1）
 * genes[1]: 2番目の都市のインデックス（0 ～ N-2）
 * genes[n-1]: N番目の都市のインデックス（0)
 *
 */


import { List } from '../../../list/lib/list';
import { BaseIndividual, BaseGeneticAlgorithm } from '../lib/base_genetic_algorithm';


class TspIndividual extends BaseIndividual {
  public num_cities: number;
  public genes: Array<number>;
  
  
  public constructor(num_cities) {
    super();

    this.num_cities = num_cities;
    this.genes = Array(this.num_cities);
    for (let i = 0; i < num_cities; i++) {
      this.genes[i] = 0;
    }
  }


  public static cities(num_cities: number): List {
    const cities = new List();
    for (let i = 0; i < num_cities; i++) {
      cities.push(String.fromCharCode('A'.charCodeAt(0) + i));
    }
    
    return cities;
  }
  
  
  public random(): TspIndividual {
    const cities = TspIndividual.cities(this.num_cities);
    
    for (let i = 0; i < this.num_cities; i++) {
      let c = Math.floor(Math.random() * cities.length);
      this.genes[i] = c;
      cities.remove(c);
    }
    
    return this;
  }
  
  
  public encode() {
    this.encoded = this.genes.map(x => `${x}`).join('_');
    return this.encoded;
  }
  
  
  public route() {
    const cities = TspIndividual.cities(this.num_cities);
    const city_ids = Array(this.num_cities);
    
    for (let i = 0; i < this.num_cities; i++) {
      let c = this.genes[i];
      let city_id = cities.remove(c);
      city_ids[i] = city_id;
      console.log(city_id);
    }
    
    return city_ids;
  }
}


class TspGA extends BaseGeneticAlgorithm {
  public static NUM_CITIES = 5;
  public start_pos: any;
  public cities: any;

  
  public constructor(config: any, start_pos: any) {
    super(config);
    
    this.start_pos = start_pos;
    
    this.cities = {
      A: {x: 10, y: 10},
      B: {x: 20, y: 20},
      C: {x: 30, y: 30},
      D: {x: 40, y: 40},
      E: {x: 50, y: 50},
    };
  }
  
  
  public fitness(ind: TspIndividual): number {
    if (ind.encoded in this.fitness_map) {
      ind.fitness = this.fitness_map[ind.encoded];
      if (ind.fitness !== null) return ind.fitness;
    }
    
    const cities = TspIndividual.cities(TspGA.NUM_CITIES);
    ind.fitness = 0;
    let pos = this.start_pos;
    for (let i = 0; i < TspGA.NUM_CITIES; i++) {
      let cid = cities.remove(ind.genes[i]);
      let next = this.cities[cid];
      let dist = Math.abs(next.x - pos.x) + Math.abs(next.y - pos.y);
      ind.fitness += dist;
      pos = next;
    }
    //console.log(ind);
    return ind.fitness;
  }
  
  
  public crossover(ind1: TspIndividual, ind2: TspIndividual):
  Array<TspIndividual> {
    const c = this.config;
    const new_ind1 = new TspIndividual(TspGA.NUM_CITIES);
    const new_ind2 = new TspIndividual(TspGA.NUM_CITIES);
    
    for (let i = 0; i < TspGA.NUM_CITIES; i++) {
      if (Math.random() > c.rate_crossover) {
	new_ind1.genes[i] = ind1.genes[i];
	new_ind2.genes[i] = ind2.genes[i];
      }
      else {
	new_ind1.genes[i] = ind2.genes[i];
	new_ind2.genes[i] = ind1.genes[i];
      }
    }

    new_ind1.encode();
    this.fitness(new_ind1);
    
    new_ind2.encode();
    this.fitness(new_ind2);
    
    return [new_ind1, new_ind2];
  }
  
  
  public mutate(ind: TspIndividual): TspIndividual {
    const c = this.config;
    const new_ind = new TspIndividual(TspGA.NUM_CITIES);
    for (let i = 0; i < TspGA.NUM_CITIES; i++) {
      new_ind.genes[i] = ind.genes[i];
      if (Math.random() > c.rate_mutate) continue;
      
      new_ind.genes[i]
	= Math.floor(Math.random() * (TspGA.NUM_CITIES - i));
    }
    
    new_ind.encode();
    this.fitness(new_ind);

    return new_ind;
  }
}


(() => {
  const config = {
    max_cities: 10,
    
    max_population: 10,
    
    rate_num_crossover: 0.5,
    rate_crossover: 0.2,
    
    rate_num_mutate: 0.5,
    rate_mutate: 0.5,

    fitness_order_by_asc: true,
    max_iteration: 20,
    timeout_msec: 30 * 1000,
  };

  const start_pos = {x: 0, y: 0};
  const ga = new TspGA(config, start_pos);
  
  const init_pop: Array<TspIndividual> = [];
  for (let i = 0; i 

■実行結果

$ ts-node tsp1.ts
TspIndividual {
  num_cities: 5,
  genes: [ 1, 1, 0, 1, 0 ],
  encoded: '1_1_0_1_0',
  fitness: 100
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 1, 0, 0, 0 ],
  encoded: '1_1_0_0_0',
  fitness: 120
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 0, 0, 1, 0 ],
  encoded: '1_0_0_1_0',
  fitness: 140
}
TspIndividual {
  num_cities: 5,
  genes: [ 2, 1, 0, 1, 0 ],
  encoded: '2_1_0_1_0',
  fitness: 140
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 1, 2, 0, 0 ],
  encoded: '1_1_2_0_0',
  fitness: 140
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 1, 1, 1, 0 ],
  encoded: '1_1_1_1_0',
  fitness: 140
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 1, 2, 1, 0 ],
  encoded: '1_1_2_1_0',
  fitness: 140
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 1, 1, 0, 0 ],
  encoded: '1_1_1_0_0',
  fitness: 160
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 0, 1, 1, 0 ],
  encoded: '1_0_1_1_0',
  fitness: 160
}
TspIndividual {
  num_cities: 5,
  genes: [ 1, 0, 2, 1, 0 ],
  encoded: '1_0_2_1_0',
  fitness: 160
}