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

``bash
npm install tycho-solver
`

Quick Start

`typescript
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

$3

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

`typescript
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());
`

$3

Memetic algorithms combine global search (genetic algorithm) with local search to refine solutions. You must provide custom operator functions (e.g., selection, crossover, mutation, evaluation, neighborhood) as part of the configuration:

`typescript
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;
},
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);
});
`

$3

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

`typescript
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);
`

$3

Parallel Local Search allows you to run multiple local searches in parallel (asynchronously) on a batch of initial solutions. This is useful for batch optimization, such as solving multiple instances of a problem or running local search from different starting points to increase the chance of finding a global optimum.

#### Example: Batch TSP Optimization

`typescript
import { ParallelLocalSearch } from 'tycho-solver';

// Suppose you have a batch of initial TSP tours
const numCities = 22;
const distances: number[][] = Array.from({ length: numCities }, (_, i) =>
Array.from({ length: numCities }, (_, j) =>
i === j ? 0 : Math.floor(Math.abs(Math.sin(i 13.37 + j 7.77)) 100 + Math.abs(i - j) 3 + 10)
)
);
// Make symmetric
for (let i = 0; i < numCities; i++) {
for (let j = i + 1; j < numCities; j++) {
distances[j][i] = distances[i][j];
}
}
type Tour = number[];

const objective = (tour: Tour) => {
let sum = 0;
for (let i = 0; i < tour.length; i++) {
sum += distances[tour[i]][tour[(i + 1) % tour.length]];
}
return sum;
};

const neighborhood = (tour: Tour) => {
const neighbors: Tour[] = [];
for (let i = 0; i < tour.length; i++) {
for (let j = i + 1; j < tour.length; j++) {
const copy = tour.slice();
[copy[i], copy[j]] = [copy[j], copy[i]];
neighbors.push(copy);
}
}
return neighbors;
};

function randomTour(): Tour {
const arr = Array.from({ length: numCities }, (_, i) => i);
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}

const batchSize = 10;
const initialTours = Array.from({ length: batchSize }, randomTour);
const options = { maxIterations: 200, maximize: false };

const pls = new ParallelLocalSearch();
pls.search(initialTours, objective, neighborhood, options).then((results) => {
results.forEach((result, idx) => {
console.log(Tour #${idx} best solution:, result.solution);
console.log(Tour #${idx} objective:, result.fitness);
});
});
`

#### API

`typescript
class ParallelLocalSearch {
search(
initialSolutions: T[],
objectiveFunction: ObjectiveFunction,
neighborhoodFunction: NeighborhoodFunction,
options?: LocalSearchOptions
): Promise[]>;
}
`

Each search is running asynchronously, and the results are returned as an array of local search results (one per initial solution).


API Documentation

$3

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

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

$3

The main class for creating and running genetic algorithms:

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

$3

A class for creating and running memetic algorithms that combine genetic algorithms with local search. You must provide all operator functions (see example above):

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

$3

A general-purpose local search algorithm implementation:

`typescript
interface ObjectiveFunction {
(solution: T): number;
}

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

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

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

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

Custom Functions and Operators

$3

When using GeneticAlgorithm, you must provide the following:

| Parameter/Operator | Signature | Description |
|-------------------|-----------|-------------|
| initialPopulation | T[] | Array of individuals to start the population |
| fitnessFunction | (individual: T) => number | Computes the fitness of an individual |

You may also provide these configuration options (see API for all):
- populationSize: number (size of the population)
- maxGenerations: number (number of generations to run)
- crossoverRate: number (probability of crossover)
- mutationRate: number (probability of mutation)
- elitism: number (number of best individuals to keep)

If your implementation allows custom selection, crossover, or mutation operators, document their signatures here as well.

$3

When using MemeticAlgorithm, you must provide the following operator functions in the configuration object:

| Operator | Signature | Description |
|-----------------------|-------------------------------------------------------|--------------------------------------------------|
| initialize | () => T | Generates a random individual |
| evaluate | (individual: T) => number | Computes the fitness of an individual |
| select | (population: Individual[]) => [Individual, Individual] | Selects parents for crossover |
| crossover | (parent1: T, parent2: T) => T | Combines two parents to produce an offspring |
| mutate | (individual: T) => T | Mutates an individual |
| neighborhoodFunction | (individual: T) => T[] | Generates neighbors for local search |

You may also provide:
- localSearchOptions: { maxIterations?: number, maximize?: boolean }
- localSearchRate: number (probability to apply local search)

See the example above for sample implementations of each operator.

$3

When using LocalSearch, you must provide the following functions:

| Function | Signature | Description |
|----------|-----------|-------------|
| objectiveFunction | (solution: T) => number | Computes the objective value (fitness) of a solution |
| neighborhoodFunction | (solution: T) => T[] | Generates neighboring solutions |

You may also provide:
- maxIterations: number (maximum number of iterations, default: 1000)
- maximize: boolean` (whether to maximize or minimize, default: true)

See the examples above for sample implementations of each function.

License

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