interface Individual {
  chromosome: number[];
  fitness: number;
}

class GeneticAlgorithm {
  private populationSize: number;
  private chromosomeLength: number;
  private mutationRate: number;
  private crossoverRate: number;
  private generations: number;
  private fitnessFunction: (chromosome: number[]) => number;

  constructor(populationSize: number, chromosomeLength: number, mutationRate: number, crossoverRate: number, generations: number, fitnessFunction: (chromosome: number[]) => number) {
    this.populationSize = populationSize;
    this.chromosomeLength = chromosomeLength;
    this.mutationRate = mutationRate;
    this.crossoverRate = crossoverRate;
    this.generations = generations;
    this.fitnessFunction = fitnessFunction;
  }

  optimize(): Individual {
    let population = this.initializePopulation();

    for (let gen = 0; gen < this.generations; gen++) {
      // 计算适应度
      population.forEach((individual) => {
        individual.fitness = this.fitnessFunction(individual.chromosome);
      });

      // 选择
      const selected = this.selection(population);

      // 交叉
      const offspring = this.crossover(selected);

      // 变异
      this.mutation(offspring);

      // 精英保留
      population = this.elitism(population, offspring);
    }

    // 返回最优解
    population.forEach((individual) => {
      individual.fitness = this.fitnessFunction(individual.chromosome);
    });

    return population.reduce((best, current) => (current.fitness > best.fitness ? current : best));
  }

  private initializePopulation(): Individual[] {
    const population: Individual[] = [];
    for (let i = 0; i < this.populationSize; i++) {
      const chromosome = [];
      for (let j = 0; j < this.chromosomeLength; j++) {
        chromosome.push(Math.random());
      }
      population.push({ chromosome, fitness: 0 });
    }
    return population;
  }

  private selection(population: Individual[]): Individual[] {
    // 轮盘赌选择
    const totalFitness = population.reduce((sum, ind) => sum + ind.fitness, 0);
    const selected: Individual[] = [];

    for (let i = 0; i < this.populationSize; i++) {
      let pick = Math.random() * totalFitness;
      for (const individual of population) {
        pick -= individual.fitness;
        if (pick <= 0) {
          selected.push({ ...individual });
          break;
        }
      }
    }

    return selected;
  }

  private crossover(parents: Individual[]): Individual[] {
    const offspring: Individual[] = [];

    for (let i = 0; i < parents.length; i += 2) {
      if (i + 1 < parents.length && Math.random() < this.crossoverRate) {
        const [child1, child2] = this.singlePointCrossover(parents[i].chromosome, parents[i + 1].chromosome);
        offspring.push({ chromosome: child1, fitness: 0 });
        offspring.push({ chromosome: child2, fitness: 0 });
      } else {
        offspring.push({ ...parents[i] });
        if (i + 1 < parents.length) {
          offspring.push({ ...parents[i + 1] });
        }
      }
    }

    return offspring;
  }

  private singlePointCrossover(parent1: number[], parent2: number[]): [number[], number[]] {
    const point = Math.floor(Math.random() * this.chromosomeLength);
    const child1 = [...parent1.slice(0, point), ...parent2.slice(point)];
    const child2 = [...parent2.slice(0, point), ...parent1.slice(point)];
    return [child1, child2];
  }

  private mutation(population: Individual[]): void {
    for (const individual of population) {
      for (let i = 0; i < this.chromosomeLength; i++) {
        if (Math.random() < this.mutationRate) {
          individual.chromosome[i] = Math.random();
        }
      }
    }
  }

  private elitism(oldPopulation: Individual[], newPopulation: Individual[]): Individual[] {
    // 保留最优个体
    const best = oldPopulation.reduce((best, current) => (current.fitness > best.fitness ? current : best));

    newPopulation.sort((a, b) => b.fitness - a.fitness);
    newPopulation[this.populationSize - 1] = { ...best };

    return newPopulation;
  }
}

// 使用示例：求函数 f(x) = x^2 的最小值，x ∈ [0, 1]
function example() {
  const ga = new GeneticAlgorithm(
    100, // 种群大小
    10, // 染色体长度
    0.01, // 变异率
    0.8, // 交叉率
    100, // 代数
    (chromosome) => {
      // 将染色体解码为 x 值
      const x = chromosome.reduce((sum, gene, index) => sum + gene * Math.pow(2, -index - 1), 0);
      return 1 / (1 + x * x); // 适应度函数（最大化）
    },
  );

  const result = ga.optimize();
  console.log('最优解:', result);
}

class SimulatedAnnealing {
  private initialTemperature: number;
  private finalTemperature: number;
  private coolingRate: number;
  private maxIterations: number;
  private objectiveFunction: (solution: number[]) => number;

  constructor(initialTemperature: number, finalTemperature: number, coolingRate: number, maxIterations: number, objectiveFunction: (solution: number[]) => number) {
    this.initialTemperature = initialTemperature;
    this.finalTemperature = finalTemperature;
    this.coolingRate = coolingRate;
    this.maxIterations = maxIterations;
    this.objectiveFunction = objectiveFunction;
  }

  optimize(initialSolution: number[]): { solution: number[]; cost: number } {
    let currentSolution = [...initialSolution];
    let currentCost = this.objectiveFunction(currentSolution);
    let bestSolution = [...currentSolution];
    let bestCost = currentCost;
    let temperature = this.initialTemperature;

    for (let iteration = 0; iteration < this.maxIterations; iteration++) {
      // 生成邻域解
      const neighborSolution = this.generateNeighbor(currentSolution);
      const neighborCost = this.objectiveFunction(neighborSolution);

      // 计算接受概率
      const deltaCost = neighborCost - currentCost;
      const acceptanceProbability = Math.exp(-deltaCost / temperature);

      // 接受新解
      if (deltaCost < 0 || Math.random() < acceptanceProbability) {
        currentSolution = [...neighborSolution];
        currentCost = neighborCost;

        // 更新最优解
        if (currentCost < bestCost) {
          bestSolution = [...currentSolution];
          bestCost = currentCost;
        }
      }

      // 降温
      temperature *= this.coolingRate;

      // 终止条件
      if (temperature < this.finalTemperature) {
        break;
      }
    }

    return { solution: bestSolution, cost: bestCost };
  }

  private generateNeighbor(solution: number[]): number[] {
    const neighbor = [...solution];
    const index = Math.floor(Math.random() * solution.length);
    // 随机扰动
    neighbor[index] += (Math.random() - 0.5) * 0.1;
    // 确保在边界内
    neighbor[index] = Math.max(0, Math.min(1, neighbor[index]));
    return neighbor;
  }
}

// 使用示例：旅行商问题 (TSP)
class TSP_SA {
  private distances: number[][];

  constructor(distances: number[][]) {
    this.distances = distances;
  }

  optimize(): { route: number[]; cost: number } {
    const n = this.distances.length;
    const initialRoute = Array.from({ length: n }, (_, i) => i);

    const sa = new SimulatedAnnealing(
      1000, // 初始温度
      0.01, // 最终温度
      0.99, // 冷却率
      10000, // 最大迭代次数
      (route) => this.calculateCost(route),
    );

    const result = sa.optimize(initialRoute);
    return { route: result.solution.map(Math.round), cost: result.cost };
  }

  private calculateCost(route: number[]): number {
    let cost = 0;
    for (let i = 0; i < route.length - 1; i++) {
      cost += this.distances[route[i]][route[i + 1]];
    }
    cost += this.distances[route[route.length - 1]][route[0]]; // 回到起点
    return cost;
  }

  private generateNeighbor(route: number[]): number[] {
    const neighbor = [...route];
    // 随机交换两个城市
    const i = Math.floor(Math.random() * route.length);
    const j = Math.floor(Math.random() * route.length);
    [neighbor[i], neighbor[j]] = [neighbor[j], neighbor[i]];
    return neighbor;
  }
}

interface Ant {
  route: number[];
  visited: Set<number>;
  currentCity: number;
  totalDistance: number;
}

class AntColonyOptimization {
  private numAnts: number;
  private numCities: number;
  private distances: number[][];
  private pheromone: number[][];
  private alpha: number; // 信息素重要程度
  private beta: number; // 启发式信息重要程度
  private rho: number; // 信息素蒸发率
  private Q: number; // 信息素强度
  private maxIterations: number;

  constructor(distances: number[][], numAnts: number, alpha: number = 1, beta: number = 2, rho: number = 0.1, Q: number = 1, maxIterations: number = 100) {
    this.numCities = distances.length;
    this.distances = distances;
    this.numAnts = numAnts;
    this.alpha = alpha;
    this.beta = beta;
    this.rho = rho;
    this.Q = Q;
    this.maxIterations = maxIterations;

    // 初始化信息素矩阵
    this.pheromone = Array(this.numCities)
      .fill(0)
      .map(() => Array(this.numCities).fill(1));
  }

  optimize(): { route: number[]; distance: number } {
    let bestRoute: number[] = [];
    let bestDistance = Infinity;

    for (let iteration = 0; iteration < this.maxIterations; iteration++) {
      const ants = this.initializeAnts();
      this.constructSolutions(ants);
      this.updatePheromone(ants);

      // 找到本代最优解
      for (const ant of ants) {
        if (ant.totalDistance < bestDistance) {
          bestDistance = ant.totalDistance;
          bestRoute = [...ant.route];
        }
      }

      // 信息素蒸发
      this.evaporatePheromone();
    }

    return { route: bestRoute, distance: bestDistance };
  }

  private initializeAnts(): Ant[] {
    const ants: Ant[] = [];
    for (let i = 0; i < this.numAnts; i++) {
      const startCity = Math.floor(Math.random() * this.numCities);
      ants.push({
        route: [startCity],
        visited: new Set([startCity]),
        currentCity: startCity,
        totalDistance: 0,
      });
    }
    return ants;
  }

  private constructSolutions(ants: Ant[]): void {
    for (const ant of ants) {
      while (ant.route.length < this.numCities) {
        const nextCity = this.selectNextCity(ant);
        if (nextCity === -1) break;

        ant.route.push(nextCity);
        ant.visited.add(nextCity);
        ant.totalDistance += this.distances[ant.currentCity][nextCity];
        ant.currentCity = nextCity;
      }

      // 回到起点
      if (ant.route.length === this.numCities) {
        ant.totalDistance += this.distances[ant.currentCity][ant.route[0]];
      }
    }
  }

  private selectNextCity(ant: Ant): number {
    const probabilities: number[] = [];
    let totalProbability = 0;

    for (let city = 0; city < this.numCities; city++) {
      if (!ant.visited.has(city)) {
        const pheromone = Math.pow(this.pheromone[ant.currentCity][city], this.alpha);
        const heuristic = Math.pow(1 / this.distances[ant.currentCity][city], this.beta);
        const probability = pheromone * heuristic;
        probabilities.push(probability);
        totalProbability += probability;
      } else {
        probabilities.push(0);
      }
    }

    if (totalProbability === 0) return -1;

    // 轮盘赌选择
    const random = Math.random() * totalProbability;
    let cumulative = 0;

    for (let i = 0; i < this.numCities; i++) {
      cumulative += probabilities[i];
      if (random <= cumulative) {
        return i;
      }
    }

    return -1;
  }

  private updatePheromone(ants: Ant[]): void {
    for (const ant of ants) {
      if (ant.route.length === this.numCities) {
        const pheromoneDeposit = this.Q / ant.totalDistance;

        for (let i = 0; i < ant.route.length - 1; i++) {
          const from = ant.route[i];
          const to = ant.route[i + 1];
          this.pheromone[from][to] += pheromoneDeposit;
          this.pheromone[to][from] += pheromoneDeposit;
        }

        // 回到起点的边
        const from = ant.route[ant.route.length - 1];
        const to = ant.route[0];
        this.pheromone[from][to] += pheromoneDeposit;
        this.pheromone[to][from] += pheromoneDeposit;
      }
    }
  }

  private evaporatePheromone(): void {
    for (let i = 0; i < this.numCities; i++) {
      for (let j = 0; j < this.numCities; j++) {
        this.pheromone[i][j] *= 1 - this.rho;
        // 防止信息素过小
        if (this.pheromone[i][j] < 0.1) {
          this.pheromone[i][j] = 0.1;
        }
      }
    }
  }
}

// 使用示例
function tspExample() {
  const distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
  ];

  const aco = new AntColonyOptimization(distances, 10);
  const result = aco.optimize();
  console.log('最优路径:', result.route);
  console.log('路径长度:', result.distance);
}

interface Particle {
  position: number[];
  velocity: number[];
  bestPosition: number[];
  bestFitness: number;
  fitness: number;
}

class ParticleSwarmOptimization {
  private numParticles: number;
  private dimensions: number;
  private maxIterations: number;
  private c1: number; // 个体学习因子
  private c2: number; // 社会学习因子
  private w: number; // 惯性权重
  private bounds: { min: number[]; max: number[] };
  private fitnessFunction: (position: number[]) => number;

  private particles: Particle[];
  private globalBestPosition: number[];
  private globalBestFitness: number;

  constructor(
    numParticles: number,
    dimensions: number,
    maxIterations: number,
    bounds: { min: number[]; max: number[] },
    fitnessFunction: (position: number[]) => number,
    c1: number = 2.0,
    c2: number = 2.0,
    w: number = 0.7,
  ) {
    this.numParticles = numParticles;
    this.dimensions = dimensions;
    this.maxIterations = maxIterations;
    this.bounds = bounds;
    this.fitnessFunction = fitnessFunction;
    this.c1 = c1;
    this.c2 = c2;
    this.w = w;

    this.particles = [];
    this.globalBestPosition = [];
    this.globalBestFitness = Infinity;

    this.initializeParticles();
  }

  optimize(): { position: number[]; fitness: number } {
    for (let iteration = 0; iteration < this.maxIterations; iteration++) {
      for (const particle of this.particles) {
        // 更新适应度
        particle.fitness = this.fitnessFunction(particle.position);

        // 更新个体最优
        if (particle.fitness < particle.bestFitness) {
          particle.bestFitness = particle.fitness;
          particle.bestPosition = [...particle.position];
        }

        // 更新全局最优
        if (particle.fitness < this.globalBestFitness) {
          this.globalBestFitness = particle.fitness;
          this.globalBestPosition = [...particle.position];
        }
      }

      // 更新粒子位置和速度
      this.updateParticles();
    }

    return {
      position: this.globalBestPosition,
      fitness: this.globalBestFitness,
    };
  }

  private initializeParticles(): void {
    for (let i = 0; i < this.numParticles; i++) {
      const position = [];
      const velocity = [];

      for (let d = 0; d < this.dimensions; d++) {
        position.push(Math.random() * (this.bounds.max[d] - this.bounds.min[d]) + this.bounds.min[d]);
        velocity.push((Math.random() - 0.5) * 2 * (this.bounds.max[d] - this.bounds.min[d]));
      }

      const fitness = this.fitnessFunction(position);
      this.particles.push({
        position,
        velocity,
        bestPosition: [...position],
        bestFitness: fitness,
        fitness,
      });

      if (fitness < this.globalBestFitness) {
        this.globalBestFitness = fitness;
        this.globalBestPosition = [...position];
      }
    }
  }

  private updateParticles(): void {
    for (const particle of this.particles) {
      for (let d = 0; d < this.dimensions; d++) {
        // 更新速度
        const r1 = Math.random();
        const r2 = Math.random();

        const cognitive = this.c1 * r1 * (particle.bestPosition[d] - particle.position[d]);
        const social = this.c2 * r2 * (this.globalBestPosition[d] - particle.position[d]);

        particle.velocity[d] = this.w * particle.velocity[d] + cognitive + social;

        // 限制速度
        const maxVelocity = (this.bounds.max[d] - this.bounds.min[d]) * 0.1;
        particle.velocity[d] = Math.max(-maxVelocity, Math.min(maxVelocity, particle.velocity[d]));

        // 更新位置
        particle.position[d] += particle.velocity[d];

        // 边界处理
        particle.position[d] = Math.max(this.bounds.min[d], Math.min(this.bounds.max[d], particle.position[d]));
      }
    }
  }
}

// 使用示例：Rastrigin 函数优化
function rastriginFunction(position: number[]): number {
  const A = 10;
  const n = position.length;
  let sum = A * n;

  for (const x of position) {
    sum += x * x - A * Math.cos(2 * Math.PI * x);
  }

  return sum;
}

function psoExample() {
  const pso = new ParticleSwarmOptimization(
    30, // 粒子数量
    2, // 维度
    100, // 最大迭代次数
    {
      // 边界
      min: [-5.12, -5.12],
      max: [5.12, 5.12],
    },
    rastriginFunction,
  );

  const result = pso.optimize();
  console.log('最优解:', result.position);
  console.log('最优值:', result.fitness);
}