CAJ | 학술논문

为了有效求解0-1背包问题,提出一种混合二进制差异演化算法.该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题.此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解.不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性.
위료유효구해0-1배포문제,제출일충혼합이진제차이연화산법.해산법기우차이연화산법광가,채용이진제편마,통과증가영사조작、S형변환조작화역영사조작등3충신적조작,장차이연화산법종실수우화영역추엄지리산우화영역,성공해결료차이연화산법직접구해리산우화문제시적계산불봉폐문제.차외,재매차질대구해시,이용탐람변환법대위반약속조건적불가행해진행변환,사기성위가행해.불동규모적배포문제적수치실험결과표명료해산법적유효성여괄용성.
In order to solve the 0-1 knapsack problem effectively,hybrid binary differential evolution algorithm is proposed.Firstly,the algorithm are added to the original differential evolution based on the original differential evolution with binary coding and three new operations which are mapping operation,Stransform operation and inverse mapping operation,The three new operations extend the original differential evolution from the continuous field to discrete field by successfully solving the no closure problem which the original differential evolution leads.Additionally,the greedy transform method is used to change the infeasible solution which violates the constraints into the feasible one.The results of 0-1 knapsack problems with different sizes solving by the hybrid binary differential evolution show it is effective and useful.