[python]Solving Knapsack Problem with Genetic Algorithm

#Copyright 2015. Aitch_K all rights reserved.
#CIST, Korea University

import random


########################################################
# - 유전자를 초기화해주는 함수
# - mChromo에 6자리로 구성된 임의의 유전자를 생성하고
#   생성된 유전자를 mChromoGrp에 저장 
# - mChromo는 임의로 생성된 각각의 염색체
# - mChromoGrp는 chromo 염색체의 그룹
########################################################
def init(mChromo, mChromoGrp):
	for i in range(chromoNum):
		mChromo = list()
		for j in range(6):
			mChromo.append(random.randrange(0, 2))
		mChromoGrp.append(mChromo)
	print mChromoGrp

	return mChromo, mChromoGrp	


########################################################
# - 본 함수는 너무 낮은 Value를 출력하는 유전자를 제거하는 함수
#   여기서 Value가 낮다는 것은 유전자가 좋지 못하다는 것을 의미
# - 본 소스는 Val의 합이 80이하일 경우 염색체를 0으로 초기화
# - 이후 Random함수를 이용해 새로운 유전자를 생성
########################################################
def lowerValChecker(mChromoGrp, mChromoSumV, mChromoSumW):
	for i in range(chromoNum):
		mChromoSumV.append(0)
		mChromoSumW.append(0)
		for j in range(6):
			mChromoSumV[i] += (v[j][mChromoGrp[i][j]])
			
	for i in range(chromoNum):
		if mChromoSumV[i] < MIN_VAL:
			mChromoSumV[i] = 0
			mChromoSumW[i] = 0

	return mChromoGrp, mChromoSumV, mChromoSumW



########################################################
# - 본 함수는 한계 Weight를 넘어가게 만드는 유전자를 제거하는 함수
# - 기본적으로 Knapsack Problem에서는 가방이 감당할 수 있는 최고 무게를 제한함
# - 본 소스에서는 Wei의 합이 120이tkd일 경우 염색체를 0으로 초기화
# - 이후 Random함수를 이용해 새로운 유전자를 생성
########################################################
def overWeiChecker(mChromoGrp, mChromoSumV, mChromoSumW):
	optWei = 0 
	for i in range(chromoNum):
		for j in range(6):
			mChromoSumW[i] += (w[j][mChromoGrp[i][j]])

	for i in range(chromoNum):
		if mChromoSumW[i] > MAX_WEI:
			mChromoSumV[i] = 0
			mChromoSumW[i] = 0

		if mChromoSumW[i] > chromoSumW[optWei]:
			optWei = i
	
	print "vList: " + str(mChromoSumV)
	print "vMax: " + str(mChromoSumV[optWei])
	print "wList: " + str(mChromoSumW)
	print "wOpt: " + str(mChromoSumW[optWei])

	return mChromoGrp, mChromoSumV, mChromoSumW


########################################################
# - 본 함수는 적당한 유전자들을 대상으로 진화를 수행하는 함수
# - 위에서 언급된 “적당한”은 너무 낮은 Val를 출력하지 않으며, 한계 Wei를 초과하지 않는 것을 의미
# - 적당하지 않아 0으로 초기화된 유전자들은 본 함수를 통해 새롭게 재생성됨
# - 유전자의 진화는 살아남은 유전자들을 대상으로 첫 번째 유전자의 3자리, 두 번째 유전자의 3자리를 결합하여 수행
#   ex) [ 0 | 0 | 1 | 0 | 1 | 0 ] + [ 0 | 1 | 0 | 1 | 0 | 0 ]
#       = [ 0 | 0 | 1 |] + [| 1 | 0 | 0 ]
########################################################
def evolutionFunc(mChromoGrp, mChromoSumV, mChromoSumW, mNewGenRsv, mNewGen):
	for i in range(len(mChromoSumV)):
		mNewGenRsv.append(0)
		mNewGenRsv[i] = list()
		if mChromoSumV[i] != 0:
			for j in range(6):
				mNewGenRsv[i].append(mChromoGrp[i][j])
		else:
			for j in range(6):
				mNewGenRsv[i].append(random.randrange(0, 2))
		
	for i in range(len(mChromoSumV)):
		mNewGen.append(mNewGenRsv[i][0:3]+mNewGenRsv[(i+1)%chromoNum][3:6])

	mChromoGrp = mNewGen

	return mChromoGrp, mChromoSumV, mChromoSumW, mNewGenRsv, mNewGen



### main routine #################################################################
chromoNum = 20
MAX_WEI = 120
MIN_VAL = 80
GENERATION = 50

v = [[0, 20], [0, 30], [0, 66], [0, 40], [0, 66], [0, 80]]
w = [[0, 10], [0, 20], [0, 30], [0, 40], [0, 50], [0, 70]]

chromo = list()
chromoGrp = list()

chromo, chromoGrp = init(chromo, chromoGrp)

for i in range(GENERATION):
	print "=============================================================="
	print "Gen " + str(i+1) 
	chromoSumV = list()
	chromoSumW = list()

	newGenRsv = list()
	newGen = list()

	print "v = [20, 30, 66, 40, 66, 80]"
	print "w = [10, 20, 30, 40, 50, 70]"

	chromoGrp, chromoSumV, chromoSumW = lowerValChecker(chromoGrp, chromoSumV, chromoSumW)
	chromoGrp, chromoSumV, chromoSumW = overWeiChecker(chromoGrp, chromoSumV, chromoSumW)
	chromoGrp, chromoSumV, chromoSumW, newGenRsv, newGen = evolutionFunc(chromoGrp, chromoSumV, chromoSumW, newGenRsv, newGen)
	
	print "==============================================================\n"