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
}

Typescript での双方向連結リスト

Typescript での双方向連結リストの実装例です。
※2024/02/25 にバグを修正

■プログラム（list.ts）

/**
 *
 * bidirectional linked list
 *
 */


export class Node {
  public obj: any;
  public prev: Node | null = null;
  public next: Node | null = null;
  
  
  constructor(obj: any) {
    this.obj = obj;
  }
}


export class List {
  public length: number = 0;
  public head: Node | null = null;
  public tail: Node | null = null;
  
  
  constructor(arr?: Array<any>) {
    if (arr === undefined) return;
    
    for (let obj of arr) {
      this.push(obj);
    }
  }


  /**
   * add node to tail
   */
  public push_node(node: Node) {
    if (this.head === null) {
      this.head = node;
    }
    
    if (this.tail !== null) {
      this.tail.next = node;
      node.prev = this.tail;
    }

    this.tail = node;
    this.length += 1;
    
    return this;
  }


  /**
   * add new obj to tail
   */
  public push(obj: any) {
    const node = new Node(obj);
    return this.push_node(node);
  }
  

  /**
   * add node to head
   */
  public unshift_node(node: Node) {
    if (this.head === null) {
      this.head = this.tail = node;
    }
    else {
      const head = this.head;
      head.prev = node;
      node.next = head;
      this.head = node;
    }
    
    this.length += 1;
    
    return this;
  }

  /**
   * add new obj to head
   */
  public unshift(obj: any) {
    const node = new Node(obj);
    return this.unshift_node(node);
  }
  

  /**
   * remove tail node
   */
  public pop_node() {
    if (this.tail === null) return null;
    
    const node = this.tail;
    this.tail = node.prev;
    if (node.prev === null) this.head = null;

    node.prev = null;
    node.next = null;
    this.length -= 1;
    
    return node;
  }


  /**
   * remove tail
   */
  public pop() {
    const node = this.pop_node();
    return node.obj;
  }
  
  
  /**
   * remove head node
   */
  public shift_node() {
    if (this.head === null) return null;
    
    // head -> node <-> next
    const node = this.head;
    this.head = node.next;
    if (this.head !== null) this.head.prev = null;
    if (node.next === null) this.tail = null;
    
    node.prev = null;
    node.next = null;
    this.length -= 1;
    
    return node;
  }
  
  
  /**
   * remove head
   */
  public shift() {
    const node = this.shift_node();
    return node.obj;
  }
  
  
  /**
   * return nth node
   */
  public nth_node(n: number) {
    if (n < 0) return null;
    if (n >= this.length) return null;
    
    let node = this.head;
    if (node === null) return null;
    
    for (let i = 0; i < n; i++) {
      if (node.next === null) return null;
      node = node.next;
    }

    if (node === null) return null;
    
    return node;
  }


  /**
   * return nth obj
   */
  public nth(n: number) {
    const node = this.nth_node(n)
    return node.obj;
  }


  /**
   * remove node
   */
  public remove_node(node: Node) {
    if (node === null) return null; // for tsc
    
    if (node.prev === null) {
      this.head = node.next;
    }
    else {
      node.prev.next = node.next;
    }
    
    if (node.next === null) {
      this.tail = node.prev;
    }
    else {
      node.next.prev = node.prev;
    }
    
    this.length -= 1;
    return node.obj;
  }
  

  /**
   * remove nth obj
   */
  public remove(n: number) {
    if (n < 0) return null;
    if (n >= this.length) return null;

    let node = this.head;
    if (node === null) return null; // for tsc
    for (let i = 0; i < n; i++) {
      if (node === null) return null; // for tsc
      node = node.next;
    }

    return this.remove_node(node);
  }


  public slice(from: number, to?: number) {
    if (from < 0) return null;
    if (from >= this.length) return null;
    if (to === undefined) to = this.length;
    if (to < 0) return null;
    if (to > this.length) return null;

    // skip head
    let node = this.head;
    if (node === null) return null; // for tsc
    for (let i = 0; i < from; i++) {
      if (node === null) return null; // for tsc
      node = node.next;
    }
    if (node === null) return null; // for tsc
    const ret_head = node;
    const head_tail = node.prev;
    
    // slice
    for (let i = from; i < to; i++) {
      if (node === null) return null; // for tsc
      node = node.next;
    }
    if (node === null) return null; // for tsc
    const ret_tail = node.prev;
    const tail_head = node;
    
    // this
    if (head_tail === null) {
      this.head = tail_head;
    }
    else {
      head_tail.next = tail_head;
    }
    
    if (tail_head === null) {
      this.tail = head_tail;
    }
    else {
      tail_head.prev = head_tail;
    }
    this.length -= (to - from);
    
    // ret
    const ret = new List();
    if (ret_head !== null) {
      ret.head = ret_head;
      ret_head.prev = null;
    }
    
    if (ret_tail !== null) {
      ret.tail = ret_tail;
      ret_tail.next = null;
    }
    
    ret.length = to - from;
    
    return ret;
  }
  
  
  public copy() {
    const new_list = new List();
    
    let node = this.head;
    while (node !== null) {
      new_list.push(node.obj);
      node = node.next;
    }
    new_list.length = this.length;
    
    return new_list;
  }


  /**
   * insert list at idx (0 - length)
   */
  public insert(idx: number, list: List) {
    if (idx < 0) return null;
    if (idx > this.length) return null;
    if (list === null) return null;
    if (list.head === null) return this;
    if (list.tail === null) return this;
    
    const new_list = list.copy();
    if (new_list.head === null) return this;
    if (new_list.tail === null) return this;
    
    if (this.head === null) this.head = new_list.head;
    if (this.tail === null) this.tail = new_list.tail;
    if (this.length === 0) {
      this.length = new_list.length;
      return this;
    }
    
    if (idx === 0) {
      const head: Node | null = this.head;
      new_list.tail.next = this.head;
      this.head = new_list.head;
      new_list.tail.next = head;
      this.length += new_list.length;
    }
    else if (idx === this.length) {
      const tail: Node | null = this.tail;
      new_list.head.prev = tail;
      tail.next = new_list.head;
      this.tail = new_list.tail;
      this.length += new_list.length;
    }
    else {
      // skip
      let node: Node | null = this.head;
      for (let i = 0; i < idx; i++) {
	if (node === null) return null;
	node = node.next;
      }
      
      // insert
      if (node === null) return null;
      const prev = node.prev;
      if (prev !== null) prev.next = new_list.head;
      new_list.head.prev = prev;
      new_list.tail.next = node;
      this.length += new_list.length;
    }
    
    return this;
  }
  
  
  public to_array() {
    const arr = new Array(this.length);
    let node = this.head;
    for (let i = 0; i < this.length; i++) {
      if (node === null) return null;
      arr[i] = node.obj;
      node = node.next;
    }
    
    return arr;
  }
}

■動作確認

import { List } from '../lib/list';

(() => {
  // push
  const list1 = new List(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']);
  list1.push('o');
  console.log(`push('o')`);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);
  
  // pop
  let obj;
  obj = list1.pop();
  console.log(`pop()`);
  console.log(obj);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);

  // unshift
  list1.unshift('-');
  console.log(`unshift('-')`);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);

  // shift
  obj = list1.shift();
  console.log(`shift()`);
  console.log(obj);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);

  // nth
  obj = list1.nth(2);
  console.log(`nth(2)`);
  console.log(obj);
  console.log(list1.to_array());

  // remove_node
  let node;
  node = list1.head;
  if (node == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${node.obj}, prev: ${node.prev}, next: ${node.next}`);
  obj = list1.remove_node(node);
  console.log(`remove_node(head)`);
  console.log(obj);
  console.log(list1.to_array());

  node = list1.head;
  if (node == null) {
    console.log('error: list1.head.next is null');
    return;
  }
  node = node.next;
  if (node == null) {
    console.log('error: list1.head.next is null');
    return;
  }
  list1.remove_node(node);
  console.log(`remove_node(head.next)`);
  console.log(list1.to_array());

  node = list1.tail;
  if (node == null) {
    console.log('error: list1.tail is null');
    return;
  }
  list1.remove_node(node);
  console.log(`remove_node(tail)`);
  console.log(list1.to_array());
  
  // remove
  obj = list1.remove(2);
  console.log(`remove(2)`);
  console.log(obj);
  console.log(list1.to_array());

  // slice
  obj = list1.slice(1, 4);
  console.log(`slice(1, 4)`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.to_array());

  // copy
  obj = list1.copy();
  console.log(`copy()`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.to_array());
  
  // insert
  const list2 = new List(['x', 'y', 'z']);
  obj = list1.insert(1, list2);
  console.log(`insert(1, ['x', 'y', 'z'])`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.length);
  
  obj = list1.insert(0, new List(['-']));
  console.log(`insert(0, ['-'])`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.length);

  obj = list1.insert(8, new List(['--']));
  console.log(`insert(8, ['--'])`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.length);

})();

■実行例

push('o')
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n', 'o'
]
15
head: obj: a, prev: null, next: [object Object]
pop()
o
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n'
]
14
head: obj: a, prev: null, next: [object Object]
unshift('-')
[
  '-', 'a', 'b', 'c',
  'd', 'e', 'f', 'g',
  'h', 'i', 'j', 'k',
  'l', 'm', 'n'
]
15
head: obj: -, prev: null, next: [object Object]
shift()
-
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n'
]
14
head: obj: a, prev: null, next: [object Object]
nth(2)
c
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n'
]
head: obj: a, prev: null, next: [object Object]
remove_node(head)
a
[
  'b', 'c', 'd', 'e',
  'f', 'g', 'h', 'i',
  'j', 'k', 'l', 'm',
  'n'
]
remove_node(head.next)
[
  'b', 'd', 'e', 'f',
  'g', 'h', 'i', 'j',
  'k', 'l', 'm', 'n'
]
remove_node(tail)
[
  'b', 'd', 'e', 'f',
  'g', 'h', 'i', 'j',
  'k', 'l', 'm'
]
remove(2)
e
[
  'b', 'd', 'f', 'g',
  'h', 'i', 'j', 'k',
  'l', 'm'
]
slice(1, 4)
[ 'd', 'f', 'g' ]
[
  'b', 'h', 'i',
  'j', 'k', 'l',
  'm'
]
copy()
[
  'b', 'h', 'i',
  'j', 'k', 'l',
  'm'
]
[
  'b', 'h', 'i',
  'j', 'k', 'l',
  'm'
]
insert(1, ['x', 'y', 'z'])
[
  'b', 'x', 'y', 'z',
  'h', 'i', 'j', 'k',
  'l', 'm'
]
10
insert(0, ['-'])
[
  '-', 'b', 'x', 'y',
  'z', 'h', 'i', 'j',
  'k', 'l', 'm'
]
11
insert(8, ['--'])
[
  '-',  'b', 'x', 'y',
  'z',  'h', 'i', 'j',
  '--', 'k', 'l', 'm'
]
12