An Ant colony optimization approach for binary knapsack problem under fuzziness

摘要

In this paper, we represent a novel ant colony optimization algorithm to solve binary knapsack problem. In the proposed algorithm for n objects, n candidate groups are created, and each candidate group has exactly m values (for m ants) as 0 or 1. For each candidate value in each group a pheromone is initialized by the value between 0.1 and 0.9, and each ant selects a candidate value from each group. Therefore, the binary solution is generated by each ant by selecting a value from each group. In each generation, pheromone update and evaporation is done. During the execution of algorithm after certain number of generation the best solution is stored as a temporary population. After that, crossover and mutation is performed between the solution generated by ants. We consider profit and weight are fuzzy in nature and taken as trapezoidal fuzzy number. Fuzzy possibility and necessity approaches are used to obtain optimal decision by the proposed ant colony algorithm. Computational experiments with different set of data are given in support of the proposed approach.