#?-*-?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