Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems (Q2505320)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems
scientific article

    Statements

    Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems (English)
    0 references
    0 references
    0 references
    4 October 2006
    0 references
    Summary: We develop and test a new approach for generating initial populations for the application of genetic algorithms (GA) to problems in combinatorial optimisation, specifically the multidimensional knapsack problem. We focus the empirical study of our approach on a set of two dimensional knapsack problems (2KP) used in a past study of 2KP algorithm performance. Our proposed approach for initial population generation focuses on generating populations that are stronger in terms of solution quality, solution diversity and in terms of solutions hovering near the border of feasible and infeasible solutions within the problem solution space. We report the results of a Monte Carlo experiment comparing our approach with the traditional initial population generation approach and report the results of computational tests involving 1120 2KP instances that cover a range of problem constraint characteristics. The collective of these computational results show that our proposed approach provides an initial population of sufficient quality and diversity to produce improved convergence to near optimal solutions which can equate to reduced computational burden in applications involving complex computations.
    0 references
    combinatorial optimisation
    0 references
    heuristics
    0 references
    multidimensional knapsack problems
    0 references
    genetic algorithms
    0 references
    genetic algorithm convergence
    0 references
    initial population generation
    0 references

    Identifiers