September $22,2024$

Problem: Consider the Linear Knapsack Problem $($LKP$)$

Maximize $f(x)={\displaystyle \underset{i=1}{\overset{16}{}}}{v}_i{x}_i$ such that

${\displaystyle \underset{i=1}{\overset{16}{}}}{w}_i{x}_{i}W$

where $x^T=(x_1,x_2,$cdots,$n),n=16,x_i$ s are the binary optimization variables. The data for

the problem are given below $,$

$(6,8),(8,14),(13,4),(15,9),(16,10),(13,11),(9,17),(25,12)$

with total capacity $W=25.$

Question $1$: Consider the above Knapsack Problem $(1)-(2)$ and construct the following

penalty function

$F(x)=f(x)-R(x)$

where $R$ is the penalty parameter and $(x)=$max$\{0,{\displaystyle \underset{j=1}{\overset{16}{}}}{w}_j{x}_j-W\}.$

Solve the problem by the binary coded Genetic Algorithm $($GA$)$ using the penalty function

$F(x)$ as your fitness function. Parameters for GA: $p_c=1,p_{}={10}^{-3},$ Population size

$N=20,$ children per iteration $m=6,$ maximum iteration $=30.$ Use the penalty parameter

$R=50$ for the fitness function.