参考资料

遗传算法--背包问题

感觉文中的代码有些许问题，按照自己的理解进行了修改，水平有限，有错欢迎指出。
1.在对fitness进行排序是，原文是是一个假排序，没有真的排序下来，
2,为选择的保留进行遗传的是将fitness最好的一般保留下来进行交叉遗传。
3.货物的信息，初始的基因我都保持了不变。

另外，感觉第一代的数据比较的时候还是有点问题，就是第一代去比较fitness的时候，总感觉有问题，因为有的时候，输出的是比第一代小的。（极少数）

代码

# -*- coding: utf-8 -*-
# @Time    :    2021/7/29 9:29
# @Author  :    LuoCheng
# @FileName:    背包修改.py 
# @Software:    PyCharm
"""
===============================================
文档功能说明：
链接：https://zerosyf.github.io/2018/10/10/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95-%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/
将背包问题转化成初始基因、初始质量价值不变的问题
===============================================
"""
import random
import pandas as pd

PACK_MAX_CAP = 1000
MAX_GENERATION = 100


def getRand():
    intnum = random.randint(0, 65535)
    return intnum


def getRand_float():
    floatnum = random.uniform(0, 1)
    return floatnum


class Good:
    def __init__(self, weight, value):
        # self.weight = weight
        self.value = value


class Entity:
    def __init__(self, goods_num):
        """
        :param goods_num: 货物的数量，也是特征的维度
        """
        self.fitness = 0
        # self.sum_weight = 0
        self.generation_id = 0
        self.gene = []
        self.initgene(goods_num)

    def initgene(self, goods_num):
        """每个个体：初始化基因，全部为 0"""
        for i in range(goods_num):
            self.gene.append(0)


class GeneAlgorithm:
    def __init__(self, grnum, cr, vr, gonum):
        self.group_num = grnum
        self.goods_num = gonum
        self.cross_rate = cr
        self.varia_rate = vr
        self.best_entity = None
        self.group = []  # 群体
        self.goods = []  # 物品
        self.initgoods()

    def get_totalfitness(self, group):
        sum = 0.0
        for i in range(len(group)):
            sum += group[i].fitness
        return sum

    def print_opt(self):
        print("最优解所在代数" + str(self.best_entity.generation_id) + "\n")
        # print("总重量" + str(self.best_entity.sum_weight) + "\n")
        print("总价值" + str(self.best_entity.fitness) + "\n")
        print("装入情况为：\n")
        for i in range(len(self.best_entity.gene)):
            print(self.best_entity.gene[i])

    def initgoods(self):
        good_info = pd.read_excel('.\背包货物信息.xlsx', sheet_name='goodinfo')
        print("物品集合信息：")
        for i in range(self.goods_num):
            self.goods.append(good_info['value'][i])
            print("物品号：" + str(i) + "价值：" + str(self.goods[i].value))

    def initgroup(self):
        self.best_entity = Entity(self.goods_num)
        for i in range(self.group_num):
            ent = Entity(self.goods_num)  # 每次初始化一个个体
            genes_info = pd.read_excel('./基因序列.xlsx')
            for i in range(self.group_num):
                ent = Entity(self.goods_num)
                ent.gene = list(genes_info.iloc[i])
                self.group.append(ent)
            # 初始化后加入种群；

    def cal_fitness(self):
        for i in range(len(self.group)):
            ent = self.group[i]
            # wei = 0;
            val = 0
            for j in range(len(ent.gene)):
                if ent.gene[j] == 1:
                    # wei += self.goods[j].weight
                    val += self.goods[j].value
            # if wei > PACK_MAX_CAP:
            #     ent.fitness = 0
            #     continue
            ent.fitness = val
            # ent.sum_weight = wei

    def recordoptimalentity(self, gid):
        sorted(self.group, key=lambda entity: entity.fitness)  # 通过fitness排序；
        ent = self.group[len(self.group) - 1]
        if ent.fitness > self.best_entity.fitness:
            self.best_entity = ent
            self.best_entity.generation_id = gid
        print("遗传代数" + str(gid) + " 总价值:" + str(ent.fitness) + "\n")

    def select(self):
        new_group = []
        selected_rate = []
        sorted(self.group, key=lambda entity: entity.fitness)
        group_num = len(self.group)
        sum_fitness = self.get_totalfitness(self.group)
        selected_rate.append(self.group[0].fitness / sum_fitness)
        for i in range(1, group_num):
            selected_rate.append(selected_rate[i - 1] + self.group[i].fitness / sum_fitness)
            # 构造轮盘；
        left_group_num = group_num * 0.5
        for i in range(int(left_group_num)):
            rand_rate = getRand_float()
            for idx in range(len(selected_rate)):
                if rand_rate <= selected_rate[idx]:
                    new_group.append(self.group[idx])
                    break;
        # 更新群体
        self.group.clear()
        self.group = new_group

    def Willcross(self):
        return (getRand_float() <= self.cross_rate)

    def cross(self):
        group_num = len(self.group)
        for i in range(0, (group_num - 1), 2):
            father = self.group[i]
            mother = self.group[i + 1]
            for j in range(len(father.gene)):
                if self.Willcross():
                    temp = father.gene[j]
                    father.gene[j] = mother.gene[j]
                    mother.gene[j] = temp
            self.group.append(father)
            self.group.append(mother)

    def Willvaria(self):
        return (getRand_float() <= self.varia_rate)

    def varia(self):
        group_num = len(self.group)
        for i in range(group_num):
            if self.Willvaria():
                ent = self.group[i]
                for j in range(len(ent.gene)):
                    if self.Willvaria():
                        if ent.gene[j] == 1:
                            ent.gene[j] == 0
                        else:
                            ent.gene[j] == 1

    def run(self):
        self.initgroup()
        for i in range(MAX_GENERATION):
            self.cal_fitness()
            self.recordoptimalentity(i)
            self.select()
            self.cross()
            if i % 5 == 0 & i != 0:
                self.varia()


if __name__ == '__main__':
    ga = GeneAlgorithm(20, 0.8, 0.5, 40)
    ga.run()
    ga.print_opt()

数据信息

货物信息

基因片段信息