每日算法 — 使用java实现克隆选择算法：免疫启发的全局优化策略

问题背景

在复杂的组合优化和函数优化问题中，传统梯度下降等方法容易陷入局部最优。进化计算（Evolutionary Computation）提供了一类基于自然启发的全局优化方法，包括遗传算法、粒子群优化、蚁群算法等。

克隆选择算法（Clonal Selection Algorithm, CLONALG）由de Castro和Von Zuben于2002年提出，模拟生物免疫系统中的克隆选择原理：
– 当病原体入侵时，免疫系统产生大量抗体
– 与抗原亲和力高的B细胞被克隆扩增（大量复制）
– 克隆过程中发生高频体细胞突变（Hypermutation）
– 高亲和力克隆被保留，低亲和力克隆被清除

这一”选择-克隆-突变-再选择”的循环，使得免疫系统能够快速适应并消灭新入侵的病原体。将这一机制抽象为优化算法，可用于求解组合优化和连续函数优化问题。

核心原理

算法参数

算法流程

1. 初始化：随机生成N个抗体（候选解）
2. 计算亲和力：评估每个抗体与目标（抗原）的匹配程度
3. 选择：选出亲和力最高的n个抗体
4. 克隆：对选中的抗体进行克隆扩增
   - 亲和力越高的抗体，克隆数量越多
5. 高频突变：对克隆体进行变异
   - 亲和力越高的抗体，变异率越低（保持优势）
   - 亲和力越低的抗体，变异率越高（鼓励探索）
6. 重新评估：计算突变后克隆体的亲和力
7. 选择：从每个抗体的克隆群体中选择最优个体替代原抗体
8. 多样性维持：替换d个最低亲和力的抗体为随机新抗体
9. 重复步骤2-8，直到满足终止条件

亲和力计算

对于函数优化：亲和力通常是目标函数值的倒数或取反（最小化问题）。

$$affinity(x) = \frac{1}{1 + f(x)} \quad \text{或} \quad affinity(x) = -f(x)$$

对于组合优化（如TSP）：亲和力可以是路径总长度的倒数。

高频突变策略

变异率与亲和力成反比：

$$mutation_rate_i = \exp(-\rho \cdot affinity_i)$$

• 高亲和力抗体：变异率低，进行局部精细搜索
• 低亲和力抗体：变异率高，进行全局探索

对于连续优化，常用高斯变异：

$$x’ = x + \alpha \cdot N(0, 1)$$

其中 $\alpha$ 与变异率成正比。

Java实现

import java.util.*;

/**
 * 克隆选择算法（CLONALG）
 * 模拟免疫系统克隆选择原理的全局优化算法
 * 适用于连续函数优化和组合优化问题
 */
public class ClonalSelectionAlgorithm {

    // 抗体（候选解）类
    public static class Antibody {
        double[] position;      // 解的位置（多维）
        double affinity;        // 亲和力（目标函数值越好，亲和力越高）
        int cloneCount;         // 该抗体的克隆数量

        public Antibody(int dim) {
            this.position = new double[dim];
            this.affinity = 0;
            this.cloneCount = 0;
        }

        public Antibody cloneAntibody() {
            Antibody clone = new Antibody(position.length);
            System.arraycopy(position, 0, clone.position, 0, position.length);
            clone.affinity = affinity;
            return clone;
        }

        @Override
        public String toString() {
            return String.format("Antibody[pos=%s, affinity=%.6f]", 
                Arrays.toString(position), affinity);
        }
    }

    // 目标函数接口
    public interface ObjectiveFunction {
        double evaluate(double[] x);
        int getDimension();
        double[] getLowerBounds();
        double[] getUpperBounds();
    }

    // 算法参数
    private int populationSize;     // 抗体种群大小N
    private int selectionSize;      // 选择克隆的抗体数量n
    private double cloneFactor;     // 克隆系数beta
    private double mutationRate;    // 基础变异率rho
    private int replacementCount;   // 每代替换的抗体数量d
    private int maxGenerations;     // 最大迭代次数
    private Random random;

    // 最优解记录
    private Antibody bestAntibody;
    private List<Double> convergenceHistory;

    public ClonalSelectionAlgorithm(int populationSize, int selectionSize,
                                     double cloneFactor, double mutationRate,
                                     int replacementCount, int maxGenerations) {
        this.populationSize = populationSize;
        this.selectionSize = selectionSize;
        this.cloneFactor = cloneFactor;
        this.mutationRate = mutationRate;
        this.replacementCount = replacementCount;
        this.maxGenerations = maxGenerations;
        this.random = new Random();
        this.convergenceHistory = new ArrayList<>();
    }

    /**
     * 主优化流程
     */
    public Antibody optimize(ObjectiveFunction func) {
        int dim = func.getDimension();
        double[] lower = func.getLowerBounds();
        double[] upper = func.getUpperBounds();

        // 步骤1：初始化种群
        List<Antibody> population = initializePopulation(dim, lower, upper);

        // 评估初始种群
        evaluatePopulation(population, func);
        updateBest(population);

        // 迭代优化
        for (int gen = 0; gen < maxGenerations; gen++) {
            // 步骤2：按亲和力排序
            population.sort((a, b) -> Double.compare(b.affinity, a.affinity));

            // 记录当前最优
            convergenceHistory.add(bestAntibody.affinity);

            // 步骤3：选择前selectionSize个抗体
            List<Antibody> selected = new ArrayList<>();
            for (int i = 0; i < selectionSize && i < population.size(); i++) {
                selected.add(population.get(i));
            }

            // 步骤4-6：克隆、突变、选择
            List<Antibody> newPopulation = new ArrayList<>();

            // 保留所有原始抗体
            for (Antibody ab : population) {
                newPopulation.add(ab.cloneAntibody());
            }

            // 对选中的抗体进行克隆扩增和突变
            for (int i = 0; i < selected.size(); i++) {
                Antibody parent = selected.get(i);
                // 克隆数量：亲和力越高（排名越靠前），克隆越多
                int clones = (int) Math.round(cloneFactor * populationSize / (i + 1));
                parent.cloneCount = clones;

                // 对该抗体的每个克隆进行突变
                for (int c = 0; c < clones; c++) {
                    Antibody clone = parent.cloneAntibody();

                    // 高频突变：亲和力越高，变异率越低
                    // mutation_strength = exp(-rho * affinity_normalized)
                    double affinityNorm = parent.affinity / (bestAntibody.affinity + 1e-10);
                    double mutStrength = Math.exp(-mutationRate * affinityNorm);

                    mutate(clone, lower, upper, mutStrength);

                    // 评估突变后的克隆体
                    double fitness = func.evaluate(clone.position);
                    clone.affinity = calculateAffinity(fitness);

                    newPopulation.add(clone);
                }
            }

            // 步骤7：从扩大的种群中选择最优N个
            newPopulation.sort((a, b) -> Double.compare(b.affinity, a.affinity));
            population = new ArrayList<>();
            for (int i = 0; i < populationSize && i < newPopulation.size(); i++) {
                population.add(newPopulation.get(i));
            }

            // 步骤8：多样性维持 - 替换最低亲和力的d个抗体
            for (int i = 0; i < replacementCount && i < population.size(); i++) {
                int idx = population.size() - 1 - i;
                Antibody newbie = new Antibody(dim);
                for (int j = 0; j < dim; j++) {
                    newbie.position[j] = lower[j] + random.nextDouble() * (upper[j] - lower[j]);
                }
                double fitness = func.evaluate(newbie.position);
                newbie.affinity = calculateAffinity(fitness);
                population.set(idx, newbie);
            }

            // 更新全局最优
            updateBest(population);

            if (gen % 50 == 0) {
                System.out.printf("Generation %d: Best Affinity = %.8f, Best Fitness = %.8f%n",
                    gen, bestAntibody.affinity, 
                    calculateFitness(bestAntibody.affinity));
            }
        }

        return bestAntibody;
    }

    /**
     * 初始化随机种群
     */
    private List<Antibody> initializePopulation(int dim, double[] lower, double[] upper) {
        List<Antibody> population = new ArrayList<>();
        for (int i = 0; i < populationSize; i++) {
            Antibody ab = new Antibody(dim);
            for (int j = 0; j < dim; j++) {
                ab.position[j] = lower[j] + random.nextDouble() * (upper[j] - lower[j]);
            }
            population.add(ab);
        }
        return population;
    }

    /**
     * 评估整个种群
     */
    private void evaluatePopulation(List<Antibody> population, ObjectiveFunction func) {
        for (Antibody ab : population) {
            double fitness = func.evaluate(ab.position);
            ab.affinity = calculateAffinity(fitness);
        }
    }

    /**
     * 计算亲和力（针对最小化问题）
     * 使用倒数变换，保证正值
     */
    private double calculateAffinity(double fitness) {
        return 1.0 / (1.0 + Math.abs(fitness));
    }

    /**
     * 从亲和力还原适应度值
     */
    private double calculateFitness(double affinity) {
        return 1.0 / affinity - 1.0;
    }

    /**
     * 高斯变异操作
     */
    private void mutate(Antibody antibody, double[] lower, double[] upper, double strength) {
        int dim = antibody.position.length;
        for (int i = 0; i < dim; i++) {
            // 高斯变异
            double mutation = strength * (upper[i] - lower[i]) * random.nextGaussian();
            antibody.position[i] += mutation;

            // 边界处理：反射法
            if (antibody.position[i] < lower[i]) {
                antibody.position[i] = lower[i] + (lower[i] - antibody.position[i]);
                if (antibody.position[i] > upper[i]) antibody.position[i] = lower[i];
            } else if (antibody.position[i] > upper[i]) {
                antibody.position[i] = upper[i] - (antibody.position[i] - upper[i]);
                if (antibody.position[i] < lower[i]) antibody.position[i] = upper[i];
            }
        }
    }

    /**
     * 更新全局最优
     */
    private void updateBest(List<Antibody> population) {
        for (Antibody ab : population) {
            if (bestAntibody == null || ab.affinity > bestAntibody.affinity) {
                bestAntibody = ab.cloneAntibody();
            }
        }
    }

    /**
     * 获取收敛历史
     */
    public List<Double> getConvergenceHistory() {
        return convergenceHistory;
    }

    // ============ 标准测试函数 ============

    /**
     * Sphere函数：f(x) = sum(x_i^2)，全局最小值0在(0,0,...,0)
     */
    public static class SphereFunction implements ObjectiveFunction {
        private int dim;
        public SphereFunction(int dim) { this.dim = dim; }
        public int getDimension() { return dim; }
        public double[] getLowerBounds() { double[] b = new double[dim]; Arrays.fill(b, -5.12); return b; }
        public double[] getUpperBounds() { double[] b = new double[dim]; Arrays.fill(b, 5.12); return b; }
        public double evaluate(double[] x) { double s = 0; for (double v : x) s += v * v; return s; }
    }

    /**
     * Rastrigin函数：多峰函数，f(x) = sum(x_i^2 - 10*cos(2*pi*x_i) + 10)
     * 全局最小值0在(0,0,...,0)，有大量局部极小值
     */
    public static class RastriginFunction implements ObjectiveFunction {
        private int dim;
        public RastriginFunction(int dim) { this.dim = dim; }
        public int getDimension() { return dim; }
        public double[] getLowerBounds() { double[] b = new double[dim]; Arrays.fill(b, -5.12); return b; }
        public double[] getUpperBounds() { double[] b = new double[dim]; Arrays.fill(b, 5.12); return b; }
        public double evaluate(double[] x) {
            double s = 0;
            for (double v : x) s += v * v - 10 * Math.cos(2 * Math.PI * v) + 10;
            return s;
        }
    }

    /**
     * Rosenbrock函数：香蕉函数，f(x) = sum(100*(x_{i+1}-x_i^2)^2 + (1-x_i)^2)
     * 全局最小值0在(1,1,...,1)，峡谷地形难以优化
     */
    public static class RosenbrockFunction implements ObjectiveFunction {
        private int dim;
        public RosenbrockFunction(int dim) { this.dim = dim; }
        public int getDimension() { return dim; }
        public double[] getLowerBounds() { double[] b = new double[dim]; Arrays.fill(b, -2.048); return b; }
        public double[] getUpperBounds() { double[] b = new double[dim]; Arrays.fill(b, 2.048); return b; }
        public double evaluate(double[] x) {
            double s = 0;
            for (int i = 0; i < dim - 1; i++) {
                s += 100 * Math.pow(x[i + 1] - x[i] * x[i], 2) + Math.pow(1 - x[i], 2);
            }
            return s;
        }
    }

    /**
     * Ackley函数：多峰函数，f(x) = -20*exp(-0.2*sqrt(1/d*sum(x_i^2))) - exp(1/d*sum(cos(2*pi*x_i))) + 20 + e
     * 全局最小值0在(0,0,...,0)
     */
    public static class AckleyFunction implements ObjectiveFunction {
        private int dim;
        public AckleyFunction(int dim) { this.dim = dim; }
        public int getDimension() { return dim; }
        public double[] getLowerBounds() { double[] b = new double[dim]; Arrays.fill(b, -32.768); return b; }
        public double[] getUpperBounds() { double[] b = new double[dim]; Arrays.fill(b, 32.768); return b; }
        public double evaluate(double[] x) {
            double sum1 = 0, sum2 = 0;
            for (double v : x) {
                sum1 += v * v;
                sum2 += Math.cos(2 * Math.PI * v);
            }
            return -20 * Math.exp(-0.2 * Math.sqrt(sum1 / dim)) 
                   - Math.exp(sum2 / dim) + 20 + Math.E;
        }
    }

    /**
     * 主函数：测试克隆选择算法
     */
    public static void main(String[] args) {
        // 算法参数
        int populationSize = 100;
        int selectionSize = 20;
        double cloneFactor = 2.0;
        double mutationRate = 2.0;
        int replacementCount = 5;
        int maxGenerations = 500;
        int dim = 10;  // 问题维度

        ClonalSelectionAlgorithm clonalg = new ClonalSelectionAlgorithm(
            populationSize, selectionSize, cloneFactor, mutationRate,
            replacementCount, maxGenerations
        );

        // 测试1：Sphere函数
        System.out.println("=== 测试1：Sphere函数（简单单峰）===");
        Antibody best1 = clonalg.optimize(new SphereFunction(dim));
        System.out.println("最优解: " + best1);
        System.out.println("目标函数值: " + new SphereFunction(dim).evaluate(best1.position));

        // 测试2：Rastrigin函数
        System.out.println("\n=== 测试2：Rastrigin函数（多峰，大量局部最优）===");
        ClonalSelectionAlgorithm clonalg2 = new ClonalSelectionAlgorithm(
            populationSize, selectionSize, cloneFactor, mutationRate,
            replacementCount, maxGenerations
        );
        Antibody best2 = clonalg2.optimize(new RastriginFunction(dim));
        System.out.println("最优解: " + best2);
        System.out.println("目标函数值: " + new RastriginFunction(dim).evaluate(best2.position));

        // 测试3：Rosenbrock函数
        System.out.println("\n=== 测试3：Rosenbrock函数（峡谷地形）===");
        ClonalSelectionAlgorithm clonalg3 = new ClonalSelectionAlgorithm(
            populationSize, selectionSize, cloneFactor, mutationRate,
            replacementCount, maxGenerations
        );
        Antibody best3 = clonalg3.optimize(new RosenbrockFunction(dim));
        System.out.println("最优解: " + best3);
        System.out.println("目标函数值: " + new RosenbrockFunction(dim).evaluate(best3.position));

        // 测试4：Ackley函数
        System.out.println("\n=== 测试4：Ackley函数（复杂多峰）===");
        ClonalSelectionAlgorithm clonalg4 = new ClonalSelectionAlgorithm(
            populationSize, selectionSize, cloneFactor, mutationRate,
            replacementCount, maxGenerations
        );
        Antibody best4 = clonalg4.optimize(new AckleyFunction(dim));
        System.out.println("最优解: " + best4);
        System.out.println("目标函数值: " + new AckleyFunction(dim).evaluate(best4.position));

        // 测试5：参数敏感性分析
        System.out.println("\n=== 测试5：参数敏感性分析（Sphere函数，不同populationSize）===");
        int[] popSizes = {20, 50, 100, 200};
        for (int popSize : popSizes) {
            ClonalSelectionAlgorithm test = new ClonalSelectionAlgorithm(
                popSize, popSize / 5, cloneFactor, mutationRate,
                popSize / 20, 200
            );
            long start = System.currentTimeMillis();
            Antibody b = test.optimize(new SphereFunction(dim));
            long time = System.currentTimeMillis() - start;
            System.out.printf("PopSize=%d: Fitness=%.10f, Time=%dms%n",
                popSize, new SphereFunction(dim).evaluate(b.position), time);
        }
    }
}

复杂度分析

时间复杂度

设种群大小为 $N$，选择数量为 $n$，问题维度为 $d$，最大迭代次数为 $G$。

• 初始化：$O(N \cdot d)$
• 每代评估：$O(N \cdot d)$（假设目标函数评估为 $O(d)$）
• 克隆扩增：克隆总数约为 $\sum_{i=1}^{n} \beta N / i = O(\beta N \log n)$
• 突变操作：$O(\text{克隆总数} \cdot d)$
• 选择替换：$O(N \log N)$

每代总复杂度：$O(\beta N \log n \cdot d)$

总复杂度：$O(G \cdot \beta N \log n \cdot d)$

空间复杂度

• 种群存储：$O(N \cdot d)$
• 克隆群体：$O(\beta N \log n \cdot d)$（峰值）

参数调优指南

应用场景

1. 函数优化：多峰函数、非凸函数、不连续函数的全局优化
2. 组合优化：TSP旅行商问题、背包问题、调度问题
3. 特征选择：从高维数据中选择最优特征子集
4. 神经网络训练：替代梯度下降进行权重优化
5. 模式识别：自动分类器和聚类中心优化

与其他进化算法的对比

混合策略：将克隆选择算法与遗传算法的交叉操作结合，或作为粒子群算法的局部搜索组件，可以获得更好的整体性能。