基于改进遗传算法的背包问题求解

针对0-1背包问题的特点,设计了一种利用定义距较长模式的遗传算子,并提出采用该算子代替交叉算子的长模式遗传算法,该算法在约束条件的处理上结合贪心法,提高了搜索效率.最后的实例仿真,给出了传统遗传算法和长模式遗传算法计算结果的比较,证明了采用新算子的遗传算法在求解0-1背包问题时比基本遗传算法有更好的收敛性能和更少的时间花费.

Solving Knapsack Problem Based on Improved Genetic Algorithms

In view of the characteristic of knapsack problem,new operator associated with longer defining length schema is designed and Long Schema Genetic Algorithm(LSGA) replaced crossover with new operator is put forward.In LSGA,the Greedy method is used to deal with the restrict condition to improve searching efficiency.At last,the simulation experiment is given,and the answer of the knapsack problem solved by Simple Genetic Algorithm and LSGA is compared.By this comparison,the advantage using new operator to solv...