首页 > 编程语言 >遗传算法解决01背包问题

遗传算法解决01背包问题

时间：2023-09-27 15:47:52浏览次数：36  
标签：popur 01 bag00 int ++ totalSize 背包 遗传算法 public

遗传算法解决01背包问题

一、问题描述

01背包问题是组合优化问题的一个典型例子，它要求在许多可行解中找到一个最优解。

01背包问题的一般描述如下：给定一个固定的背包容量和一组物品，每个物品有一个重量和一个价值，要求从这组物品中选择一些放入背包，使得背包中物品的总价值最大，同时不超过背包的容量。

01背包问题的定义。

给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。目标是从这些物品中挑选一些放入背包，使得背包内物品的总价值最大化，同时不超过背包的容量限制C。在挑选物品时，对于每个物品i只能选择放入或不放入背包，不能重复放入或只放入一部分。

二、遗传算法

1、遗传算法的基本思想

遗传算法是一种模拟自然进化过程的优化方法，它从一个称为种群的候选解集合开始，通过不断地产生新的种群来寻找更优的解。

遗传算法的核心是选择、交叉和变异三种操作。

  • 选择是根据解的适应度来从旧种群中挑选出一些解作为双亲，适应度越高，被选中的概率越大。
  • 交叉是将两个双亲的部分特征进行组合，产生新的解作为后代。
  • 变异是对某些解的某些特征进行随机改变，增加种群的多样性。

这个迭代产生新种群的过程一直持续到遗传算法达到预设的终止条件为止。这就是遗传算法的基本原理。

2、遗传算法的基本元素。

遗传算法是由以下几个要素构成的：

  1. 一个由染色体编码的候选解组成的种群，每个染色体代表一个可行解；
  2. 一个根据染色体的适应度评估其优劣的适应度函数，适应度越高，染色体越优；
  3. 一个根据适应度选择染色体作为双亲的选择机制，适应度越高，被选中的概率越大；
  4. 一个通过交换双亲染色体的部分基因产生新染色体的交叉操作，交叉可以增加种群的多样性和创新性；
  5. 一个对某些染色体的某些基因进行随机变化的变异操作，变异可以防止种群陷入局部最优。

这些要素共同构成了遗传算法的基本框架。

例题1：

背包容量为9，物品重量 w={2,3,4,5}，其价值是v={3,4,5,7}}。

1 编码：

针对01背包问题，我们设计了一种染色体编码方法：将待求解的n个决策变量
$$
{x1,x2,...,xn}
$$
表示为长度为n的二进制字符串
$$
x[j]，j=1，2， …，n。
$$

x[j]=0表示第j个物品不放入背包，x[j]=1表示第j个物品放入背包。

例如：1010代表一个可行解，它表示将第1、3号物品放入背包，其余的物品则不放入。

2 生成初始种群：

在这个例子中，我们设定种群规模为4，也就是说种群由4个个体构成，每个个体可以用随机的方式生成。例如：
a1 = [1, 1, 1, 1]
a2 = [1, 0, 1, 0]
a3 = [1, 0, 0, 1]
a4 = [1, 0, 0, 0]

3 种群适应度计算：

按照下列公式计算种群中个体适应度：
$$
TotalSize=Σwixi
$$

$$
\left.Fitness=\left{\begin{array}{ll}\Sigma v_ix_i&TotalSize\leq C\\Sigma v_ix_i-alpha*(TotalSize-C)&TotalSize>C\end{array}\right.\right.
$$

公式的下半部分即为适应度的惩罚函数，其中参数alpha>1.0。在本例中我们取alpha=2。

a1 = [1, 1, 1, 1], totalSize = 14, totalValue = 19, fit = 9
a2 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fit = 8
a3 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fit = 10
a4 = [1, 0, 0, 0], totalSize = 2, totalValue = 3, fit = 3

4 选择：

为了确定每个个体在下一代种群中复制的数量，我们采用了一种与适应度成正比的概率选择方法。具体操作过程如下：

  1. 先计算出群体中所有个体的适应度的总和
    $$
    Σf(ai)
    ，i=1,2,3,4
    $$

  2. 接下来，我们计算每个个体的相对适应度
    $$
    p(ai)=f(ai)/Σf(ai)
    ，i=1,2,3,4
    $$
    这就是每个个体被遗传到下一代种群的概率。

  3. 每个概率值组成一个区间，全部概率值之和为1；

  4. 最后，我们再生成一个0到1之间的随机数，根据该随机数落在哪个概率区间内来确定哪个个体被选中。在这个例子中，

$$
Σf(ai)=30
$$

p(a1)=30.00 %， p(a2)=26.66%，p(a3)=33.33%，p(a4)=10.00%

因此a1区间=[0,0.3]，a2区间=[0.3,0.5666]，a3区间=[0.5666,0.9]，a4区间=[0.9,1]。经过4次选择，a3被选1次，a2被选2次，a4落选:

b1 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8
b2 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fitValue = 10
b3 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8
b4 = [1, 1, 1, 1], totalSize = 14, totalValue = 19, fitValue = 9

5交叉：

  • 本例采用单点交叉的方法，其具体操作过程如下：
    • 首先，将种群中的个体随机配对；
    • 其次，为每对个体随机设定一个交叉点位置；
    • 最后，让每对个体在交叉点处相互交换部分基因。 在这个例子中， b1与b4在第3位后交叉，生成：

c1 = [1, 0, 1, 1], totalSize = 11, totalValue = 15, fitValue = 11
c2 = [1, 1, 1, 0], totalSize = 9, totalValue = 12, fitValue = 12

b2与b3在第2位后交叉，生成：

c3 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8
c4 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fitValue = 10

6 突变：

我们采用基本位变异的方法来进行变异运算，其具体操作过程如下：

  • 首先，随机确定每个个体的一个变异位位置；
  • 然后，按照一定的概率将变异位上的基因值取反。 在这个例子中， c1的第1位发生变异：

c1 = [0, 0, 1, 1], totalSize = 9, totalValue = 12, fitValue = 12
c2 = [1, 1, 1, 0], totalSize = 9, totalValue = 12, fitValue = 12
c3 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8
c4 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fitValue = 10
————————————————
至此，我们已经找到了2个最优解c1与c2

代码如下

package work3;

import java.util.ArrayList;
import java.util.Collections;

//工具类
public class FitnessTool {

    /**
     * 计算背包总重
     *
     * @param gene01 染色体基因01
     * @param w      物品重
     * @param count  基因数/物品数
     * @return
     */
    public static int totalSize(int[] gene01, int[] w, int count) {
        int total = 0;
        for (int i = 0; i < count; i++) {
            total += (gene01[i] * w[i]);
        }
        return total;
    }

    /**
     * 计算种群中个体适应度
     *
     * @param C         背包容量
     * @param gene01    染色体基因01
     * @param v         物品价值
     * @param totalSize 背包总重
     * @param count     基因数
     * @return
     */
    public static int fitness(int C, int[] gene01, int[] v, int totalSize, int count) {
        int alpha = 2;
        int fitness = 0;
        for (int i = 0; i < count; i++) {
            fitness += (gene01[i] * v[i]);
        }
        if (totalSize <= C) {
            return fitness;
        } else {
            return fitness - alpha * (totalSize - C);
        }
    }


    /**
     * 每个个体被遗传到下一代群体中的概率
     *
     * @param fitnessInt 所有个体的适应度数组
     * @param amount     种群数
     * @return
     */
    public static double[] geneticProbability(int[] fitnessInt, int amount) {
        int totalFitness = 0;
        double[] probability = new double[amount];
        for (int i = 0; i < amount; i++) {
            totalFitness += fitnessInt[i];
        }
        for (int i = 0; i < amount; i++) {
            probability[i] = (double) fitnessInt[i] / totalFitness;
        }
        return probability;
    }

    /**
     * 依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数
     *
     * @param probability 每个个体被遗传到下一代群体中的概率
     * @param amount      种群数
     * @return 各个个体被选中的次数数组
     */
    public static int[] numberOfSelections(double[] probability, int amount) {
        int[] number = new int[amount];

        for (int i = 0; i < amount; i++) {
            double random = Math.random();

            if (probability[0] > random) {
                number[0]++;
            }
            if (probability[0] + probability[1] > random && probability[0] < random) {
                number[1]++;
            }
            if (probability[0] + probability[1] + probability[2] > random && probability[0] + probability[1] < random) {
                number[2]++;
            }

            if (probability[1] + probability[2] + probability[0] < random) {
                number[3]++;
            }
        }
        return number;
    }

    /**
     * 经过选择过后，得到新的染色体组
     *
     * @param popur              旧的染色体组
     * @param numberOfSelections 各个个体被选中的次数数组
     * @return 新的染色体组
     */
    public static int[][] newPopur(int[][] popur, int[] numberOfSelections) {
        int number;
        int first = 0;
        int[][] newPopur = new int[popur.length][popur[0].length];
        for (int i = 0; i < popur.length; i++) {
            number = numberOfSelections[i];

            if (number == 4) {
                for (int j = 0; j < popur[0].length; j++) {
                    newPopur[first][j] = popur[i][j];
                }
                first++;
            }
            if (number >= 3) {
                for (int j = 0; j < popur[0].length; j++) {
                    newPopur[first][j] = popur[i][j];
                }
                first++;
            }
            if (number >= 2) {
                for (int j = 0; j < popur[0].length; j++) {
                    newPopur[first][j] = popur[i][j];
                }
                first++;
            }
            if (number >= 1) {
                for (int j = 0; j < popur[0].length; j++) {
                    newPopur[first][j] = popur[i][j];
                }
                first++;
            }

        }
        return newPopur;
    }

    /**
     * 显示种群的染色体组
     */
    public static void readPopur(int[][] popur) {
        for (int i = 0; i < popur.length; i++) {
            for (int j = 0; j < popur[i].length; j++) {
                System.out.print(popur[i][j] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 显示1个一维数组
     *
     * @param OneArray
     */
    public static void readOneArray(int[] OneArray) {
        for (int i :
                OneArray) {
            System.out.print(i + "\t");
        }
    }

    /**
     * 单点交叉的方法
     *
     * @param popur 交叉前染色体组
     * @return 交叉后染色体组
     */
    public static int[][] crossPopur(int[][] popur) {
        int[] crossNumber = new int[popur.length];
        int[][] newPopur = new int[popur.length][popur[0].length];//一定要new，不然就是多一个命名，但是是同一个数组

        //使染色体组乱序
        //创建从小到大的数组
        ArrayList list = new ArrayList(popur.length);
        for (int i = 0; i < popur.length; i++) {
            list.add(i);
        }
        //使数组乱序
        Collections.shuffle(list);
        //使染色体组乱序
        for (int i = 0; i < popur.length; i++) {
            crossNumber[i] = (int) list.get(i);
            for (int j = 0; j < popur[0].length; j++) {
                newPopur[i][j] = popur[crossNumber[i]][j];
            }
        }

        //确定交叉点
        int[] temp = new int[popur[0].length];
        for (int i = 0; i < popur.length; i += 2) {
            int intersection = (int) (Math.random() * popur[0].length);

            for (int j = intersection; j < popur[0].length; j++) {
                temp[j] = newPopur[i][j];
                newPopur[i][j] = newPopur[i + 1][j];
                newPopur[i + 1][j] = temp[j];
            }
        }
        return newPopur;
    }

    /**
     * 对染色体组采用基本位变异的方法来进行变异
     *
     * @param popur 染色体组
     * @return 变异后的染色体组
     */
    public static int[][] variation(int[][] popur) {

        int[] varPupor = new int[popur.length];//变异的个体

        for (int i = 0; i < popur.length; i++) {
            varPupor[i] = (int) (Math.random() + 0.2);
        }

        int varPosition = (int) (Math.random() * popur[0].length);//变异的位置
        for (int i = 0; i < popur.length; i++) {
            if (varPupor[i] == 1) {
                popur[i][varPosition] = popur[i][varPosition] > 0 ? 0 : 1;
            }
        }
        return popur;
    }
}
===========
package work3;

//物品类
public class Goods {

    int[] w = {2, 3, 4, 5};//物品重量
    int[] v = {3, 4, 5, 7};//物品价值

    public Goods() {

    }


    public int[] getW() {
        return w;
    }

    public void setW(int[] w) {
        this.w = w;
    }

    public int[] getV() {
        return v;
    }

    public void setV(int[] v) {
        this.v = v;
    }
}
===========
    package work3;
//染色体类
public class Chromosome {

    private int count;//物品数量

    public Chromosome() {
    }

    public Chromosome(int count) {
        this.count = count;
    }

    /**
     * 一个染色体上的基因显示
     *
     * @return
     */
    public int[] getGene01() {
        int[] x = new int[count];
        for (int i = 0; i < count; i++) {
            x[i] = (int) (Math.random() + 0.5);
        }
        return x;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }
}
==========
    package work3;

//背包类
public class Bag00 {
    int C = 9;//背包容量
    int amount;//种群数量
    int[][] popur;//染色体组01
    Chromosome chromosome;//染色体

    public Bag00(int amount, int count) {
        this.amount = amount;
        chromosome = new Chromosome(count);
        getPopur();

    }


    /**
     * 生成种群的染色体组
     *
     * @return 种群的染色体组01
     */
    public int[][] getPopur() {
        int[] gene01;
        popur = new int[this.amount][chromosome.getCount()];
        for (int i = 0; i < amount; i++) {
            for (int j = 0; j < chromosome.getCount(); j++) {
                gene01 = chromosome.getGene01();
                popur[i][j] = gene01[j];
            }
        }
        return popur;
    }

    /**
     * 显示种群的染色体组
     */
    public void readPopur() {
        for (int i = 0; i < amount; i++) {
            for (int j = 0; j < chromosome.getCount(); j++) {
                System.out.print(popur[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

======
    package work3;

//背包装物品
public class BagSet {

    Bag00 bag00;
    Goods goods;

    public BagSet() {
        bag00 = new Bag00(4, 4);
        System.out.println("\n初始种群\n");
        bag00.readPopur();//初始种群
        System.out.println("========");
        goods = new Goods();
    }

    /**
     * 经过一次遗传得到的染色体组
     *
     * @return
     */
    public int[][] flowPath() {
        int[] totalSize = new int[bag00.amount];
        int[] fitness = new int[bag00.amount];
        //计算总重与适应度
        for (int i = 0; i < bag00.amount; i++) {
            totalSize[i] = FitnessTool.totalSize(bag00.popur[i], goods.w, bag00.chromosome.getCount());
            fitness[i] = FitnessTool.fitness(bag00.C, bag00.popur[i], goods.v, totalSize[i], bag00.chromosome.getCount());
        }
        System.out.println("\n总重{2,3,4,5}\n");
        FitnessTool.readOneArray(totalSize);
        System.out.println("\n适应度{3,4,5,7}\n");
        FitnessTool.readOneArray(fitness);
        //每个个体被遗传到下一代群体中的概率
        double[] geneticProbability = FitnessTool.geneticProbability(fitness, bag00.amount);
        //个体被选中的次数
        System.out.println("\n个体被选中的次数\n");
        int[] numberOfSelections = FitnessTool.numberOfSelections(geneticProbability, bag00.amount);
        FitnessTool.readOneArray(numberOfSelections);

        System.out.println("\n经过选择过后，得到新的染色体组\n");

        int[][] newPopur = FitnessTool.newPopur(bag00.popur, numberOfSelections);
        FitnessTool.readPopur(newPopur);

        System.out.println("\n交叉后染色体组\n");
        int[][] crossPopur = FitnessTool.crossPopur(newPopur);
        FitnessTool.readPopur(crossPopur);

        System.out.println("\n变异后的染色体组\n");
        int[][] variation = FitnessTool.variation(newPopur);
        FitnessTool.readPopur(variation);
        return variation;

    }

    /**
     * 经过500次遗传得到的染色体组
     *
     * @return
     */
    public int[][] flowPath50() {
        int[] totalSize = new int[bag00.amount];
        int[] fitness = new int[bag00.amount];
        int[][] variation = new int[bag00.amount][bag00.chromosome.getCount()];
        ;
        for (int i = 0; i < 500; i++) {
            //计算总重与适应度
            for (int j = 0; j < bag00.amount; j++) {
                totalSize[j] = FitnessTool.totalSize(bag00.popur[j], goods.w, bag00.chromosome.getCount());
                fitness[j] = FitnessTool.fitness(bag00.C, bag00.popur[j], goods.v, totalSize[j], bag00.chromosome.getCount());
            }

            //每个个体被遗传到下一代群体中的概率
            double[] geneticProbability = FitnessTool.geneticProbability(fitness, bag00.amount);
            //个体被选中的次数

            int[] numberOfSelections = FitnessTool.numberOfSelections(geneticProbability, bag00.amount);

            //经过选择过后，得到新的染色体组
            int[][] newPopur = FitnessTool.newPopur(bag00.popur, numberOfSelections);

            //交叉后染色体组
            int[][] crossPopur = FitnessTool.crossPopur(newPopur);

            //变异后的染色体组
            variation = FitnessTool.variation(crossPopur);
        }
        return variation;

    }

    /**
     * 计算染色体组的总重与适应度
     *
     * @param popur
     */
    public void calaFitness(int[][] popur) {
        int[] totalSize = new int[bag00.amount];
        int[] fitness = new int[bag00.amount];
        //计算总重与适应度
        for (int i = 0; i < bag00.amount; i++) {
            totalSize[i] = FitnessTool.totalSize(popur[i], goods.w, bag00.chromosome.getCount());
            fitness[i] = FitnessTool.fitness(bag00.C, popur[i], goods.v, totalSize[i], bag00.chromosome.getCount());
        }
        System.out.println("\n总重{2,3,4,5}\n");
        FitnessTool.readOneArray(totalSize);
        System.out.println("\n适应度{3,4,5,7}\n");
        FitnessTool.readOneArray(fitness);
    }
}
====
    package work3;

//主函数启动

public class TestBags1 {
    public static void main(String[] args) {
        BagSet bagSet = new BagSet();
        int[][] flowPath = bagSet.flowPath50();
        System.out.println();
        System.out.println("========");
        FitnessTool.readPopur(flowPath);//显示最终的染色体组
        bagSet.calaFitness(flowPath);//显示最终的染色体组的适应度
    }
}

显示效果

第一次运行

初始种群

1	1	1	0	
0	0	1	0	
1	0	0	0	
0	0	0	0	
========

最终的染色体组

0	0	1	1	
1	1	1	0	
0	0	1	0	
1	0	0	0	

总重{2,3,4,5}

9	9	4	2	
适应度{3,4,5,7}

12	12	5	3

第二次运行

初始种群

1	0	0	1	
1	1	0	0	
1	1	1	0	
1	0	1	1	
========

最终的染色体组

1	0	1	0	
1	1	0	1	
1	0	1	1	
1	0	1	1	

总重{2,3,4,5}

6	10	11	11	
适应度{3,4,5,7}

8	12	11	11

标签：popur,01,bag00,int,++,totalSize,背包,遗传算法,public
From： https://www.cnblogs.com/xin-zhi-suo-xiang/p/17732852.html

相关文章

  • PX01如何通过LcdTools读取IC值自动生成初始化代码
    在点屏调试中我们会碰到这种情况，一个已经烧录过全代码的屏在没有获取他的全代码的情况下，怎么从IC里面读取生成初始化代码下到其他屏？LcdTools可以完美解决上述问题，下面举例说明操作过程。首先，我们需要熟悉DriverIC，有哪些寄存器地址，如何进行寄存器读写，我们以ILI9881C为例;ILI988......
  • 代码随想录day21 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 2
    530.二叉搜索树的最小绝对差classSolution{private:intresult=INT_MAX;TreeNode*pre=NULL;voidtraversal(TreeNode*cur){if(cur==NULL)return;traversal(cur->left);//左if(pre!=NULL){//中......
  • 安徽合肥琦鸿高分子选购我司HS-TGA-101热重分析仪
    安徽合肥琦鸿高分子材料有限公司，一家专注于高分子材料研发、生产和销售的企业，在近期选购了我司的HS-TGA-101热重分析仪。 安徽合肥琦鸿高分子材料有限公司对于原材料的品质把控严格，对热重分析仪的需求十分明确：需要一款精度高、稳定性好的热重分析仪，用于研究高分子材料的热性能，以便......
  • 在Linux课程中所学01
    今天在大学期间一节Linux课程中，我学习到了一些基本的命令记录一下less命令命令也是对文件或其他输出进行分页显示，可用pageup、pagedown与键盘方向键控制，查找文件内容比more更容易，最后按q键退出。head命令有些配置文件内容很多，但真正需要查看的内容只有前几行，head命令可以查看......
  • VS2019安装PCL 1.11.1
    1.从官网下载PCL：https://github.com/PointCloudLibrary/pcl/releases 下载这两个文件就行2.安装运行下载好的exe进行安装，注意这一步要选第二个添加到系统变量，一直下一步安装到默认路径即可： 我这里安装的时候选成了第一个，但是没关系，安装好后再系统变量的Path里添加： 然......
  • JavaSE day01【复习回顾面向对象基础、继承、抽象类】测评
    选择题题目1(单选):下列关于Java中类与类之间的关系描述正确的是()选项:​ A.Java中类与类属于多继承,还可以多层继承​ B.Java中类与类属于实现关系,可以单实现也可以多实现​ C.Java中类与类属于实现关系,可以只能单实现​ D.Java中类与类属于单继承,......
  • 第01章：随堂复习与企业真题（Java语言概述）
    第01章：随堂复习与企业真题（Java语言概述）一、随堂复习1.Java基础全程的学习内容第1阶段：Java基本语法>Java概述、关键字、标识符、变量、运算符、流程控制（条件判断、选择结构、循环结构）、IDEA、数组第2阶段：Java面向对象编程>类及类的内部成员>面向对象的三大特征>其它......
  • 尚硅谷_第01章_Java语言概述
    第01章_Java语言概述拓展练习讲师：尚硅谷-宋红康网址：www.atguigu.com1、System.out.println()和System.out.print()有什么区别？System.out.println();//打印完后，会换行。System.out.print();//打印完后，不会换行。2、一个".java"源文件中是否可以包括多个类？有什么限制？......
  • 01 - Rust 猜数字游戏
    目录1.猜数字游戏的逻辑2.创建新项目3.猜数字游戏实现3.1获取用户输入并打印a.标准库引入b.println!宏c.可变与不可变变量d.string::new与io::stdin().read_line(&mutinput)3.2生成指定范围内的随机数3.3随机数与猜测数的比较a.字符串转数字b.数字比较大小c.循环......
  • 多线程Review-926-01
    一、进程与线程1、进程：①电脑管家等软件我们运行的应用程序②在内存中正在运行的程序2、线程：①进程中的一个最小执行单元。一个进程最少得有一个线程②软件中的每一个功能，如电脑管家中的清理垃圾、杀毒、软件搜索二、线程的创建方式1、继承Thread类  ：优点——代码......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99