CAJ | 학술논문

对0/1背包问题进行研究，提出一种自适应元胞粒子群算法。在算法设计过程中，重新定义粒子位置和速度的更新方程，引入自适应因子，为有效粒子的主动进化和无效粒子的主动退化提供依据，新的编码方式使得新产生的粒子能够以更大的概率和更快的速度成为有效粒子，将元胞及其邻居引入到算法中保持种群的多样性，利用元胞的演化规则进行局部优化，避免算法陷入局部极值。对多组不同规模的背包问题进行仿真实验，结果表明，该算法不仅可以有效求解0/1背包问题，而且能够以较快的速度搜索到精度较高的次优解甚至全局最优解，具有较好的稳定性。
대0/1배포문제진행연구，제출일충자괄응원포입자군산법。재산법설계과정중，중신정의입자위치화속도적경신방정，인입자괄응인자，위유효입자적주동진화화무효입자적주동퇴화제공의거，신적편마방식사득신산생적입자능구이경대적개솔화경쾌적속도성위유효입자，장원포급기린거인입도산법중보지충군적다양성，이용원포적연화규칙진행국부우화，피면산법함입국부겁치。대다조불동규모적배포문제진행방진실험，결과표명，해산법불부가이유효구해0/1배포문제，이차능구이교쾌적속도수색도정도교고적차우해심지전국최우해，구유교호적은정성。
0/1 knapsack problem is studied,and adaptive cellular particle swarm optimization algorithm is presented. In the design of the algorithm,the rules about updating the particle’ s velocity and position are redefined,an adaptive factor is introduced to provide a basis for the active evolution of the valid particle and the active degradation of the invalid particle,a new coding mode is given to make new particles be valid with great probability and fast speed,cellular and its neighbor are introduced into the algorithm to maintain the swarm’ s diversity and the algorithm uses evolutionary rule of cellular in local optimization to avoid local optima. Simulation experimental results of different scale 0/1 knapsack problem and comparisons with other algorithms show that the algorithm not only can solve the 0/1 knapsack problem effectively,but also can get the good second-best solution even for the global optimal solution with a faster rate,and has a certain degree of stability.