经典遗传算法（SGA）解01背包问题的python代码实现

经典遗传算法(SGA)解01背包问题的python代码实现，说明如下： 1.采用经典的二进制编码，选择算子为轮盘赌选择，交叉算子为两点交叉，变异算子为反转（单点）变异 2.可调的参数为：gen,pc,pm,popsize,n,w,c,W,M 3.两种解码方式：带惩罚项和不带惩罚项

# -*- coding: utf-8 -*-
“““
程序功能：实现经典的遗传算法解决01背包问题
说明：
1.采用经典的二进制编码，选择算子为轮盘赌选择，交叉算子为两点交叉，变异算子为反转（单点）变异
2.可调的参数为：genpcpmpopsizenwcWM（168行起）
3.修改解码方式请改177行，1-第一种解码方式，2-第二种解码方式（惩罚项）
作者：（晓风）wangchao
email: 18821709267@163.com 
最初建立时间：2018.10.25
最近修改时间：2018.10.25

GA的简单实现
“““
import numpy as np
import matplotlib.pyplot as plt

#初始化种群
def init（popsizen）: 
    population=[]
    for i in range（popsize）:
        pop=‘‘
        for j in range（n）:
            pop=pop+str（np.random.randint（02））
        population.append（pop）    
    return population

#解码1
def decode1（xnwcW）:
    s=[]#储存被选择物体的下标集合
    g=0
    f=0
    for i in range（n）:
        if （x[i] == ‘1‘）:
            if g+w[i] <= W:
                g = g+w[i]
                f = f+c[i]
                s.append（i）
            else:
                break
    return fs

#适应度函数1
def fitnessfun1（populationnwcW）:
    value=[]
    ss=[]
    for i in range（len（population））:
        [fs]= decode1（population[i]nwcW）
        value.append（f）
        ss.append（s）
    return valuess

#解码2
def decode2（xnwc）:
    s=[]#储存被选择物体的下标集合
    g=0
    f=0
    for i in range（n）:
        if （x[i] == ‘1‘）:
            g = g+w[i]
            f = f+c[i]
            s.append（i）
    return gfs

#适应度函数2
def fitnessfun2（populationnwcWM）:
    value=[]
    ss=[]
    for i in range（len（population））:
        [gfs]= decode2（population[i]nwc）
        if g>W:
            f = -M*f#惩罚
        value.append（f）
        ss.append（s）
    minvalue=min（value）
    value=[（i-minvalue+1） for i in value]
    return valuess


#轮盘赌选择
def roulettewheel（populationvaluepop_num）:
    fitness_sum=[]
    value_sum=sum（value）
    fitness=[i/value_sum for i in value]
    for i in range（len（population））:##
        if i==0:
            fitness_sum.append（fitness[i]）
        else:
            fitness_sum.append（fitness_sum[i-1]+fitness[i]）
    population_new=[]
    for j in range（pop_num）:###
        r=np.random.uniform（01）
        for i in range（len（fitness_sum））:###
            if i==0:
                if r>=0 and r<=fitness_sum[i]:
                    population_new.append（population[i]）
            else:
                if r>=fitness_sum[i-1] and r<=fitness_sum[i]:
                    population_new.append（population[i]）
    return population_new

#单点交叉
def crossover（population_newpcncross）:
    a=int（len（population_new）/2）
    parents_one=population_new[:a]
    parents_two=population_new[a:]
    np.random.shuffle（parents_one）
    np.random.shuffle（parents_two）
    offspring=[]
    for i in range（a）:
        r=np.random.uniform（01）
        if r<=pc:
            point1=np.random.randint（0（len（parents_one[i]）-1））
            point2=np.random.randint（point1len（parents_one[i]））
            off_one=parents_one[i][:point1]+parents_two[i][point1:point2]+parents_one[i][point2:]
            off_two=parents_two[i

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-10-25 13:18  sga解01背包问题代码\
     文件        8521  2018-10-25 12:32  sga解01背包问题代码\sga.py
     文件        8540  2018-10-25 12:30  sga解01背包问题代码\sga2.py