A genetic algorithm is applied to the 0/1 multiple knapsack problem. Experiments are performed to investigate the effects of re-ordering the problem sets, and biasing the initial solution strings to increase the probability of certain items being selected. Re-ordering is based on the value/weight ratio and weight variance of the items. Experiments to bias the initial solution strings increased the probability of selecting high value/weight ratio and variance items, as well as items known to be in the optimal solution. The algorithm is tested using well-known test problems from the literature. Results of experiments show that re-ordering had limited impact on finding the optimal solution. Increasing the probability of certain items did affect the outcome of the algorithm. However, just choosing an item known to be in the optimal solution and increasing its probability of being selected did not necessarily result in the optimal solution being discovered more frequently.
展开▼
