基于编码转换的离散演化算法设计与应用

为了利用演化算法求解离散域上的组合优化问题，借鉴遗传算法（GA）、二进制粒子群优化（BPSO）和二进制差分演化（HBDE）中的映射方法，提出了一种基于映射变换思想设计离散演化算法的实用方法——编码转换法（ETM），并利用一个简单有效的编码转化函数给出了求解组合优化问题的离散演化算法一般算法框架A-DisEA.为了说明ETM的实用性与有效性，首先基于A-DisEA给出了一个离散粒子群优化算法（DisPSO），然后分别利用BPSO、HBDE和DisPSO等求解集合联盟背包问题和折扣{0-1}背包问题，通过对计算结果的比较表明：BPSO、HBDE和DisPSO的求解性能均优于GA，这不仅说明基于ETM的离散演化算法在求解KP问题方面具有良好的性能，同时也说明利用ETM方法设计离散演化算法是一种简单且有效的实用方法.

Design and Applications of Discrete Evolutionary Algorithm Based on Encoding Transformation

In order to solve a combinatorial optimization problem in discrete domains by using evolutionary algorithms, draw lessons from the design concept of genetic algorithm (GA), binary particle swarm optimization (BPSO) and binary differential evolution with hybrid encoding (HBDE), we propose a simple and practical method for designing discrete evolution algorithm based on the idea of mapping transformation. This method is named Encoding Transformation Method (ETM). A framework of discrete evolution algorithm named A-DisEA is advanced by using a simple and effective encoding conversion function. For illustrating the practicability and effectiveness of ETM, a discrete particle swarm optimization (DisPSO) algorithm based on ETM is proposed. Then, we use GA, BPSO, HBDE and DisPSO to solve the set union knapsack problem (SUKP) and the discounted {0-1} knapsack problem (D{0-1}KP), respectively. The results show that for SUKP and D{0-1}KP, the discrete evolutionary algorithms based on ETM, i.e. BPSO, HBDE and DisPSO have better performance than GA. this indicates that the ETM is not only a feasible method, but also a very practical and efficient method.