遺伝的アルゴリズムでナップザック問題を解く

参考文献

「機械学習と深層学習―C言語によるシミュレーション―」2016/05/21
(著)小高 知宏
文献元

準備

console

pip install numpy

ソースコード

sample.py

# -*- coding: utf-8 -*-
#/*****************************************************/
#/*                  kpga.c　　                       */
#/*　ナップサック問題のＧＡによる求解プログラム       */
#/*ＧＡによって、ナップサック問題の最良解を探索します */
#/*****************************************************/
import numpy as np


#/*記号定数の定義*/
MAXVALUE    = 100            #/*重さと価値の最大値*/
N           = 50             #/*荷物の個数*/
WEIGHTLIMIT = (N*MAXVALUE/4) #/*重量制限*/
POOLSIZE    = 30             #/*プールサイズ*/
LASTG       = 100            #/*打ち切り世代*/
MRATE       = 0.01           #/*突然変異の確率*/
SEED        = 32767          #/*乱数のシード*/
YES         = 1              #/*yesに対応する整数値*/
NO          = 0              #/*noに対応する整数値*/

#/*******************/
#/*    main()関数   */
#/*******************/
def main():
 pool=np.full((POOLSIZE,N),0) #/*染色体プール*/
 ngpool=np.full((POOLSIZE*2,N),0) #/*次世代染色体プール*/
 generation=0#/* 現在の世代数 */
 parcel=np.full((N,2),0)#/*荷物*/
 #/*乱数の初期化*/
 np.random.seed(None)
 
 #/*荷物の初期化*/
 parcel=initparcel(parcel)
 
 #/*初期集団の生成*/
 pool=initpool(pool)
 
 #/*打ち切り世代まで繰り返し*/
 for i in range(LASTG):
  generation+=1
  print("世代",generation)
  ngpool=mating(pool,ngpool,parcel) #/*交叉*/
  ngpool=mutation(ngpool) #/*突然変異*/
  pool=selectng(ngpool,pool,parcel) #/*次世代の選択*/
  printp(pool,parcel) #/*結果出力*/
 


#/****************************/
#/*      initparcel()関数    */
#/*　    荷物の初期化   　   */
#/****************************/
def initparcel(parcel):
 i=0
 parcel=np.random.randint(1,9,(N,2))
 print("parcel",parcel)
 return parcel

#/************************/
#/*   selectng()関数     */
#/*   次世代の選択       */
#/************************/
def selectng(ngpool,pool,parcel):
 i=j=c=0#/* 繰り返しの制御変数 */
 totalfitness=0#/*適応度の合計値*/
 roulette=np.full((POOLSIZE*2,),0)#/*適応度を格納*/
 ball=0#/* 玉（選択位置の数値）*/
 acc=0#/*適応度の積算値*/
 
 #/*選択を繰り返す*/
 for i in range(POOLSIZE):
  #/* ルーレットの作成 */
  totalfitness=0
  for c in range(POOLSIZE*2):
   roulette[c]=evalfit(ngpool[c],parcel)
   #/* 適応度の合計値を計算*/
   totalfitness+=roulette[c]
  
  #/*染色体を一つ選ぶ*/
  ball=rndn(totalfitness)
  acc=0
  d=0
  for c in range(POOLSIZE*2):
   acc+=roulette[c]#/*適応度を積算*/
   if acc>ball:
    d=c
    break#/*対応する遺伝子*/
  
  #/*染色体のコピー*/
  for j in range(N):
   pool[i][j]=ngpool[d][j]
 return pool
 

#/************************/
#/*   selectp()関数      */
#/*    親の選択          */
#/************************/
def selectp(roulette,totalfitness):
 i=0   #/* 繰り返しの制御変数 */
 ball=0#/* 玉（選択位置の数値）*/
 acc=0 #/*適応度の積算値*/
 ball=rndn(totalfitness)
 for i in range(POOLSIZE):
  acc+=roulette[i]#/*適応度を積算*/
  if acc>ball:
  	break#/*対応する遺伝子*/
 return i



#/************************/
#/*   mating()関数       */
#/*        交叉          */
#/************************/
def mating(pool,ngpool,parcel):
 i=0#/* 繰り返しの制御変数 */
 totalfitness=0#/*適応度の合計値*/
 roulette=np.full((POOLSIZE,),0)#/*適応度を格納*/
 mama=papa=0#/*親の遺伝子の番号*/

 #/* ルーレットの作成 */
 for i in range(POOLSIZE):
  roulette[i]=evalfit(pool[i],parcel)
  #/* 適応度の合計値を計算*/
  totalfitness+=roulette[i]
 #/*選択と交叉を繰り返す*/
 for i in range(POOLSIZE):
  while True:#/*重複の削除*/#/*親の選択*/
   #print("totalfitness",totalfitness)
   mama=selectp(roulette,totalfitness)
   papa=selectp(roulette,totalfitness)
   #print("mama,papa,",mama,papa)
   if mama!=papa:
    break
  
  #/*特定の２遺伝子の交叉*/
  ngpool[i*2],ngpool[i*2+1]=crossing(pool[mama],pool[papa],ngpool[i*2],ngpool[i*2+1])
 
 return ngpool


#/************************/
#/*  crossing()関数      */
#/* 特定の２染色体の交叉 */
#/************************/
def crossing(m,p,c1,c2):
 j=0#/* 繰り返しの制御変数 */
 cp=0#/*交叉する点*/

 #/*交叉点の決定*/
 cp =rndn(N)

 #/*前半部分のコピー*/
 for j in range(cp):
  c1[j]=m[j]
  c2[j]=p[j]
  
 i=range(cp)
 #/*後半部分のコピー*/
 for j in range(cp,N,1):
  c2[j]=m[j]
  c1[j]=p[j]
 return c1,c2

#/************************/
#/*   evalfit()関数      */
#/*   適応度の計算       */
#/************************/
def evalfit(g,parcel):
 pos=0#/*遺伝子座の指定*/
 value=0#/*評価値*/
 weight=0#/*重量*/
 #print("parcel,",parcel)
 #/*各遺伝子座を調べて重量と評価値を計算*/
 for pos in range(N):
  weight+=parcel[pos][0]*g[pos]
  value+=parcel[pos][1]*g[pos]
 #/*致死遺伝子の処理*/
 if weight>=WEIGHTLIMIT:
  value=0
 return value
 

#/***********************/
#/*   printp()関数      */
#/*   結果出力          */
#/***********************/
def printp(pool,parcel):
 i=j=0#/* 繰り返しの制御変数 */
 fitness=0#/* 適応度 */
 totalfitness=0.#/* 適応度の合計値 */
 elite=bestfit=0#/*エリート遺伝子の処理用変数*/

 for i in range(POOLSIZE):
  fitness=evalfit(pool[i],parcel)
  if fitness>bestfit:#/*エリート解*/
   bestfit=fitness
   elite=i
  totalfitness+=fitness
 print("pool",pool)
 #/*エリート解の適応度を出力*/
 print("elite,bestfit",elite,bestfit)
 #/*平均の適応度を出力*/
 print("totalfitness",totalfitness/POOLSIZE)
 


#/***********************/
#/*   initpool()関数    */
#/*   初期集団の生成    */
#/***********************/
def initpool(pool):
 i=j=0#/* 繰り返しの制御変数 */
 for i in range(POOLSIZE):
  for j in range(N):
   pool[i][j]=rndn(2)
 return pool

#/************************/
#/*     rndn()関数       */
#/*    n未満の乱数の生成 */
#/************************/
def rndn(l):
 rndno=0#/*生成した乱数*/
 if l!=0:
  while True:
   rndno=np.random.randint(0,l)
   if rndno==l:
    continue
   else:
    break
 return rndno

#/***********************/
#/*   mutation()関数    */
#/*   突然変異          */
#/***********************/
def mutation(ngpool):
 i=j=0#/* 繰り返しの制御変数 */

 for i in range(POOLSIZE*2):
  for j in range(N):
   if np.double(rndn(100))/100.<=MRATE:
    #/*反転の突然変異*/
    ngpool[i][j]=notval(ngpool[i][j])
 return ngpool


#/************************/
#/*   notval()関数       */
#/*   真理値の反転       */
#/************************/
def notval(v):
 if v==YES:
  return NO
 else:
  return YES

main()