Tycho Solver

A modular and extensible library for evolutionary computation and optimization problems.

Features

• Genetic Algorithm implementation
• Configurable selection, crossover and mutation operators
• TypeScript support with full type definitions
• Modular architecture for easy extension

Installation

npm install tycho-solver

Quick Start

import { GeneticAlgorithm } from 'tycho-solver';

// Define a simple problem: find a list of numbers that sum to a target value
const target = 100;
const populationSize = 50;
const numGenes = 10;

// Initialize with random numbers between 0 and 20
const initialPopulation = Array.from({ length: populationSize }, () => 
  Array.from({ length: numGenes }, () => Math.floor(Math.random() * 21))
);

// Fitness function: higher is better when sum is closer to target
const fitnessFunction = (individual: number[]) => {
  const sum = individual.reduce((a, b) => a + b, 0);
  return 1000 - Math.abs(sum - target);
};

// Configure and run the genetic algorithm
const ga = new GeneticAlgorithm(
  initialPopulation,
  fitnessFunction,
  {
    populationSize: populationSize,
    maxGenerations: 100,
    crossoverRate: 0.8,
    mutationRate: 0.2
  }
);

// Run the evolution
const solution = ga.evolve();
console.log('Best solution:', solution);
console.log('Fitness:', ga.getBestFitness());

Examples

Genetic Algorithm

The genetic algorithm is ideal for problems where you need to find solutions in a large search space:

import { GeneticAlgorithm } from 'tycho-solver';

// Example: Binary knapsack problem
// Items with values and weights
const items = [
  { value: 4, weight: 12 },
  { value: 2, weight: 2 },
  { value: 10, weight: 4 },
  { value: 1, weight: 1 },
  { value: 2, weight: 2 }
];
const maxWeight = 15;

// Initialize a random population (0 = item not taken, 1 = item taken)
const populationSize = 50;
const initialPopulation = Array.from({ length: populationSize }, () => 
  Array.from({ length: items.length }, () => Math.round(Math.random()))
);

// Fitness function - evaluate each solution
const fitnessFunction = (individual: number[]) => {
  const totalValue = individual.reduce((sum, gene, index) => 
    sum + (gene * items[index].value), 0);
  const totalWeight = individual.reduce((sum, gene, index) => 
    sum + (gene * items[index].weight), 0);

  // Return 0 fitness if solution exceeds weight constraint
  return totalWeight <= maxWeight ? totalValue : 0;
};

// Configure and run the genetic algorithm
const ga = new GeneticAlgorithm(
  initialPopulation,
  fitnessFunction,
  {
    populationSize: populationSize,
    maxGenerations: 100,
    crossoverRate: 0.8,
    mutationRate: 0.1,
    elitism: 2 // Keep the best 2 individuals
  }
);

// Run the evolution
const solution = ga.evolve();
console.log('Best solution:', solution);
console.log('Fitness:', ga.getBestFitness());

Memetic Algorithm

Memetic algorithms combine global search (genetic algorithm) with local search to refine solutions:

import { MemeticAlgorithm } from 'tycho-solver';

// Example: Traveling Salesman Problem (TSP)
const cities = [
  { x: 60, y: 200 },
  { x: 180, y: 200 },
  { x: 80, y: 180 },
  { x: 140, y: 180 },
  { x: 20, y: 160 },
  { x: 100, y: 160 },
  { x: 200, y: 160 }
];

const distance = (city1, city2) => {
  return Math.sqrt(Math.pow(city1.x - city2.x, 2) + Math.pow(city1.y - city2.y, 2));
};

const memeticOptions = {
  populationSize: 30,
  generations: 50,
  crossoverRate: 0.9,
  mutationRate: 0.2,
  localSearchRate: 0.3,
  initialize: () => {
    const indices = Array.from({ length: cities.length }, (_, i) => i);
    for (let i = indices.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [indices[i], indices[j]] = [indices[j], indices[i]];
    }
    return indices;
  },
  evaluate: (route) => {
    let totalDistance = 0;
    for (let i = 0; i < route.length; i++) {
      const from = cities[route[i]];
      const to = cities[(route[(i + 1) % route.length])];
      totalDistance += distance(from, to);
    }
    return 1000 / totalDistance;
  },
  select: (population) => {
    const tournament = (size = 3) => {
      const contestants = Array.from({ length: size }, () =>
        population[Math.floor(Math.random() * population.length)]
      );
      return contestants.reduce((best, ind) =>
        ind.fitness > best.fitness ? ind : best, contestants[0]
      );
    };
    return [tournament(), tournament()];
  },
  crossover: (parent1, parent2) => {
    const size = parent1.length;
    const start = Math.floor(Math.random() * size);
    const end = start + Math.floor(Math.random() * (size - start));
    const offspring = Array(size).fill(-1);
    for (let i = start; i <= end; i++) {
      offspring[i] = parent1[i];
    }
    let j = (end + 1) % size;
    for (let i = 0; i < size; i++) {
      const nextPos = (end + 1 + i) % size;
      if (offspring[nextPos] === -1) {
        while (offspring.includes(parent2[j])) {
          j = (j + 1) % size;
        }
        offspring[nextPos] = parent2[j];
      }
    }
    return offspring;
  },
  mutate: (genome) => {
    const genomeCopy = [...genome];
    const idx1 = Math.floor(Math.random() * genomeCopy.length);
    let idx2 = Math.floor(Math.random() * genomeCopy.length);
    while (idx1 === idx2) {
      idx2 = Math.floor(Math.random() * genomeCopy.length);
    }
    [genomeCopy[idx1], genomeCopy[idx2]] = [genomeCopy[idx2], genomeCopy[idx1]];
    return genomeCopy;
  },
  objectiveFunction: (route) => {
    let totalDistance = 0;
    for (let i = 0; i < route.length; i++) {
      const from = cities[route[i]];
      const to = cities[(route[(i + 1) % route.length])];
      totalDistance += distance(from, to);
    }
    return 1000 / totalDistance;
  },
  neighborhoodFunction: (route) => {
    const neighbors = [];
    for (let i = 0; i < route.length - 1; i++) {
      for (let j = i + 1; j < route.length; j++) {
        const newRoute = [...route];
        let left = i;
        let right = j;
        while (left < right) {
          [newRoute[left], newRoute[right]] = [newRoute[right], newRoute[left]];
          left++;
          right--;
        }
        neighbors.push(newRoute);
      }
    }
    return neighbors.slice(0, 10);
  },
  localSearchOptions: {
    maxIterations: 20,
    maximize: true
  }
};

// Run the memetic algorithm as a class
const memetic = new MemeticAlgorithm(memeticOptions);
memetic.initializePopulation().then(async () => {
  const bestSolution = await memetic.evolve();
  console.log('Best route:', bestSolution.genome);
  console.log('Fitness:', bestSolution.fitness);
});

Local Search

Local search algorithms are useful for refining solutions or solving optimization problems directly:

import { LocalSearch } from 'tycho-solver';

// Example: Function optimization - find minimum of a 2D function
// Function to optimize: f(x,y) = (x-2)² + (y-3)² + 1
const objectiveFunction = (solution: [number, number]): number => {
  const [x, y] = solution;
  return Math.pow(x - 2, 2) + Math.pow(y - 3, 2) + 1;
};

// Neighborhood function - generate nearby points
const neighborhoodFunction = (solution: [number, number]): [number, number][] => {
  const [x, y] = solution;
  const stepSize = 0.1;

  return [
    [x + stepSize, y],
    [x - stepSize, y],
    [x, y + stepSize],
    [x, y - stepSize],
    [x + stepSize, y + stepSize],
    [x - stepSize, y - stepSize],
    [x + stepSize, y - stepSize],
    [x - stepSize, y + stepSize]
  ];
};

// Create and configure the local search
const localSearch = new LocalSearch<[number, number]>();

// Initial solution [0, 0]
const initialSolution: [number, number] = [0, 0];

// Run the search
const result = localSearch.search(
  initialSolution,
  objectiveFunction,
  neighborhoodFunction,
  {
    maxIterations: 1000,
    maximize: false // We're minimizing the function
  }
);

console.log('Best solution found:', result.solution);
console.log('Objective value:', result.fitness);
console.log('Iterations performed:', result.iterations);

API Documentation

Core Types

// Fitness function that evaluates the quality of a solution
type FitnessFunction<T> = (individual: T) => number;

// Configuration options for evolutionary algorithms
interface EvolutionaryConfig {
  populationSize: number;
  maxGenerations: number;
  selectionPressure?: number;
  mutationRate?: number;
  crossoverRate?: number;
  elitism?: number;
}

GeneticAlgorithm

The main class for creating and running genetic algorithms:

class GeneticAlgorithm<T> implements EvolutionaryAlgorithm<T> {
  constructor(initialPopulation: T[], fitnessFunction: FitnessFunction<T>, config: EvolutionaryConfig);
  evolve(generations?: number): T;
  getBestSolution(): T;
  getBestFitness(): number;
  getPopulation(): T[];
  getGeneration(): number;
}

MemeticAlgorithm

A class for creating and running memetic algorithms that combine genetic algorithms with local search:

class MemeticAlgorithm<T> {
  constructor(config: MemeticOptions<T>);
  initializePopulation(): Promise<void>;
  evolve(): Promise<Individual<T>>;
  getBestIndividual(): Individual<T>;
  getPopulation(): Individual<T>[];
}

LocalSearch

A general-purpose local search algorithm implementation:

interface ObjectiveFunction<T> {
  (solution: T): number;
}

interface NeighborhoodFunction<T> {
  (solution: T): T[];
}

interface LocalSearchOptions {
  maxIterations?: number;  // Default: 1000
  maximize?: boolean;  // Default: true
}

interface LocalSearchResult<T> {
  solution: T;  // Best solution found
  fitness: number;  // Objective value of the best solution
  iterations: number;  // Number of iterations performed
}

class LocalSearch<T> {
  search(
    initialSolution: T,
    objectiveFunction: ObjectiveFunction<T>,
    neighborhoodFunction: NeighborhoodFunction<T>,
    options?: LocalSearchOptions
  ): LocalSearchResult<T>;
}

License

This project is licensed under the Mozilla Public License 2.0 - see the LICENSE file for details.