遗传算法计划生产计划排序java

遗传算法是一种启发式优化算法，可以用于解决排列问题，例如计划生产计划排序。下面是一个简单的遗传算法实现计划生产计划排序的Java代码：

import java.util.Arrays;
import java.util.Random;

public class GeneticAlgorithm {
    private static final int POPULATION_SIZE = 100;
    private static final double MUTATION_RATE = 0.1;
    private static final double CROSSOVER_RATE = 0.9;
    private static final int TOURNAMENT_SIZE = 5;
    private static final int ELITISM_COUNT = 1;

    private static final int[][] productionPlan = {{1, 2, 3, 4, 5}, {2, 1, 4, 5, 3}, {3, 5, 2, 1, 4}, {4, 3, 5, 2, 1}, {5, 4, 1, 3, 2}};
    private static final int[] demands = {20, 30, 15, 25, 10};

    private static final Random random = new Random();

    private static int[][] generateInitialPopulation() {
        int[][] population = new int[POPULATION_SIZE][5];
        for (int i = 0; i < POPULATION_SIZE; i++) {
            population[i] = generateRandomChromosome();
        }
        return population;
    }

    private static int[] generateRandomChromosome() {
        int[] chromosome = {1, 2, 3, 4, 5};
        for (int i = 0; i < chromosome.length; i++) {
            int j = random.nextInt(chromosome.length);
            int temp = chromosome[i];
            chromosome[i] = chromosome[j];
            chromosome[j] = temp;
        }
        return chromosome;
    }

    private static int[][] selectParents(int[][] population) {
        int[][] parents = new int[2][];
        for (int i = 0; i < 2; i++) {
            int[] tournament = new int[TOURNAMENT_SIZE];
            for (int j = 0; j < TOURNAMENT_SIZE; j++) {
                tournament[j] = random.nextInt(POPULATION_SIZE);
            }
            int best = tournament[0];
            for (int j = 1; j < TOURNAMENT_SIZE; j++) {
                if (fitness(population[tournament[j]]) > fitness(population[best])) {
                    best = tournament[j];
                }
            }
            parents[i] = population[best];
        }
        return parents;
    }

    private static int[] crossover(int[] parent1, int[] parent2) {
        int[] child = new int[parent1.length];
        int startPos = random.nextInt(parent1.length);
        int endPos = random.nextInt(parent1.length);
        if (startPos > endPos) {
            int temp = startPos;
            startPos = endPos;
            endPos = temp;
        }
        for (int i = startPos; i <= endPos; i++) {
            child[i] = parent1[i];
        }
        int j = 0;
        for (int i = 0; i < parent2.length; i++) {
            if (!contains(child, parent2[i])) {
                while (child[j] != 0) {
                    j++;
                }
                child[j++] = parent2[i];
            }
        }
        return child;
    }

    private static boolean contains(int[] array, int value) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                return true;
            }
        }
        return false;
    }

    private static void mutate(int[] chromosome) {
        for (int i = 0; i < chromosome.length; i++) {
            if (random.nextDouble() < MUTATION_RATE) {
                int j = random.nextInt(chromosome.length);
                int temp = chromosome[i];
                chromosome[i] = chromosome[j];
                chromosome[j] = temp;
            }
        }
    }

    private static int fitness(int[] chromosome) {
        int[] production = new int[5];
        for (int i = 0; i < chromosome.length; i++) {
            for (int j = 0; j < 5; j++) {
                production[j] += productionPlan[chromosome[i] - 1][j];
            }
        }
        int fitness = 0;
        for (int i = 0; i < 5; i++) {
            fitness += Math.min(production[i], demands[i]);
        }
        return fitness;
    }

    private static int[][] sortPopulation(int[][] population) {
        Arrays.sort(population, (chromosome1, chromosome2) -> fitness(chromosome2) - fitness(chromosome1));
        return population;
    }

    private static int[][] nextGeneration(int[][] population) {
        int[][] newPopulation = new int[POPULATION_SIZE][5];
        for (int i = 0; i < ELITISM_COUNT; i++) {
            newPopulation[i] = population[i];
        }
        for (int i = ELITISM_COUNT; i < POPULATION_SIZE; i++) {
            int[][] parents = selectParents(population);
            int[] child = crossover(parents[0], parents[1]);
            mutate(child);
            newPopulation[i] = child;
        }
        return newPopulation;
    }

    public static void main(String[] args) {
        int[][] population = generateInitialPopulation();
        for (int i = 0; i < 1000; i++) {
            population = nextGeneration(population);
            population = sortPopulation(population);
            System.out.println("Generation: " + i + ", Best fitness: " + fitness(population[0]));
        }
        System.out.println("Best production plan: " + Arrays.toString(population[0]));
    }
}

在这个代码中，我们首先定义了一些常量，包括种群大小、突变率、交叉率、锦标赛大小和精英计数。然后我们定义了一个二维数组productionPlan表示每个工厂生产每种产品的数量，以及一个一维数组demands表示每种产品的需求量。

generateInitialPopulation方法用于生成初始种群，其中每个染色体是一个长度为5的排列。

selectParents方法使用锦标赛选择算法来选择两个父母，即从种群中随机选择TOURNAMENT_SIZE个个体，然后选择其中适应度最高的个体作为父母。

crossover方法实现单点交叉，即随机选择一个起始位置和一个结束位置，将第一个父母的这段子串复制到子代中，然后将第二个父母中未被复制的基因按照原来的顺序填充到子代中。

mutate方法实现基因突变，即对每个基因以MUTATION_RATE的概率进行交换。

fitness方法计算染色体的适应度，即根据每个工厂生产的产品数量计算满足需求的产品数量之和。

sortPopulation方法按照适应度从高到低对种群进行排序。

nextGeneration方法生成下一代种群，包括精英计数个最适应的染色体和其余染色体通过交叉和突变生成。

最后，在main方法中运行遗传算法，迭代1000代，并输出每一代的最适应染色体的适应度和最佳方案。