|
|
問題
重さと価値がそれぞれW[i],V[i]であるようなN個の品物がある。
これらの品物から、重さの総和がAを超えないように選んだとき、
価値の総和の最大値を求めよ。
●総当り
LET N=8 !種類
DATA 7,3,2,6,1,5,10,3 !重さ
DATA 8,4,3,10,7,9,5,2 !価値
LET A=20
DIM W(N),V(N)
MAT READ W
MAT READ V
LET VMAX=0
FOR P=0 TO 2^N-1 !全パターン
LET WW=0
LET VV=0
LET B=P
LET i=1
DO WHILE B>0
LET WW=WW+MOD(B,2)*W(i)
LET VV=VV+MOD(B,2)*V(i)
LET B=INT(B/2)
LET i=i+1
LOOP
IF WW<=A AND VV>VMAX THEN LET VMAX=VV
NEXT P
PRINT "価値=";VMAX
END
●貧欲法
「その場での最善」を選択することを繰り返す。シンプルで高速である。
LET N=8 !種類
DATA 7,3,2,6,1,5,10,3 !重さ
DATA 8,4,3,10,7,9,5,2 !価値
LET A=20
DIM W(N),V(N)
MAT READ W
MAT READ V
LET VMAX=0
DO WHILE A>0
LET Vi=0
FOR i=1 TO N
IF W(i)<=A AND V(i)>Vi THEN !価値が最も大きいもの
LET Vi=V(i)
EXIT FOR !最初に見つかったもの
END IF
NEXT i
IF i>N THEN EXIT DO !条件を満たすものが既にない場合
LET VMAX=VMAX+Vi
LET A=A-W(i) !除外して次へ
LET V(i)=0 !※最小値
LOOP
PRINT "価値=";VMAX
END
●動的計画法（Dynamic Programming、DP）
LET N=8 !種類
DATA 7,3,2,6,1,5,10,3 !重さ
DATA 8,4,3,10,7,9,5,2 !価値
LET A=20
DIM W(N),V(N)
MAT READ W
MAT READ V
DIM DP(0 TO A)
FOR i=1 TO N
LET j=A
DO WHILE j>=W(i)
LET DP(j)=MAX(DP(j),DP(j-W(i))+V(i))
LET j=j-1
LOOP
NEXT i
MAT PRINT DP; !DP(A)
END
●遺伝的アルゴリズム
RANDOMIZE
LET N=8 !種類
DATA 7,3,2,6,1,5,10,3 !重さ
DATA 8,4,3,10,7,9,5,2 !価値
LET A=20
DIM W(N),V(N)
MAT READ W
MAT READ V
FUNCTION F(X,W()) !適応度
LET FF=0
LET ii=1
LET XX=X
DO WHILE XX>0 !10進法から2進法へ
LET FF=FF+MOD(XX,2)*W(ii)
LET XX=INT(XX/2)
LET ii=ii+1
LOOP
LET F=FF
END FUNCTION
LET M=4 !個体数 ※Mは2以上
DIM X(M) !個体
FOR i=1 TO M !第0世代
LET X(i)=INT(RND*2^N) !0から2^N-1まで
NEXT i
MAT PRINT X; !debug
DIM NX(M) !次の世代
FOR t=1 TO 10 !世代交代によって進化させる
!選択淘汰（Selection）
!※エリート選択による適応度がベスト1,2（一番大きな数から順に2つ）の2個体
LET T1=-999 !1番目 値は-∞
LET T2=T1
FOR i=1 TO M
LET WK=F(X(i),V)
IF F(X(i),W)>A THEN LET WK=0 !制限を越えるなら解ではないので、0とする
IF WK>T1 THEN
LET T2=T1 !降格
LET X2=X1
LET T1=WK !ベスト1
LET X1=i
ELSE
IF WK>T2 THEN
LET T2=WK !ベスト2
LET X2=i
END IF
END IF
NEXT i
LET NX(1)=X(X1)
LET NX(2)=X(X2)
!上記の2個体を親として、各々の染色体について交叉（Cross Over）させた2個体
!※親Aa,Bb → 子Ab,Ba
LET P=2^INT(N/2)
LET NX(3)=INT(NX(1)/P)*P+MOD(NX(2),P)
LET NX(4)=INT(NX(2)/P)*P+MOD(NX(1),P)
FOR i=1 TO M !次の世代へ
LET X(i)=NX(i)
!各々の染色体について0.05の確率で遺伝子を変異させる
!※上位と下位を入れ替える（1点逆位） Aa → aA
IF RND<0.05 THEN
LET P=3 ! !突然変異（Mutation） 1～[N/2]
LET X(i)=INT(X(i)/2^P)+MOD(X(i),2^P)*2^(N-P)
END IF
NEXT i
NEXT t
MAT PRINT X; !debug
PRINT BSTR$(X(1),2) !進化の結果
PRINT "重さ=";F(X(1),W)
PRINT "価値=";F(X(1),V)
END
|
|