韩雪山

摘要：本文基于遗传算法，通过对适应度函数的设计，提出了一种新的改进的遗传算法，用于解决从N个候选方案中选择M（1

Abstract： Based on the genetic algorithm with the design of fitness function， this paper proposes a new improved genetic algorithm to address the problem of select M （1

关键词：遗传算法;组合优化;多约束;适应度函数;供应商选择

Key words： genetic algorithm;combined optimization;multiple constraints;fitness function;supplier selection

中图分类号：F274                                          文献标识码：A                                  文章编号：1006-4311（2020）14-0123-02

0  引言

从理论上来讲，针对解空间有限而数量特别巨大的组合优化问题，可以通过枚举法得出优化解，但实际上却是非常的麻烦。遗传算法具有全局的搜索能力，与传统的枚举法相比，具有很快的收敛速度的优势，因而许多学者将遗传算法引入到组合优化问题中。但是针对具有多个约束条件限制下的从N个候选方案中选择M个的最优组合问题，通过设计相应的适应度函数来求解的文献却很少。

本文据此基于遗传算法，通过对遗传算法中编码和适应度函数的设计，提出了一种新的改进的遗传算法，并将其应用到供应商选择的案例中，具有很强的现实意义。

1  改进的遗传算法

1.1 遗传算子的设计

编码。本文采用实数编码，将个体的每个基因值用某一范围内的一个实数来表示，个体的编码长度就等于变量的个数。

适应度函数的构造。本文采用变化的适应度函数的方案，将问题的约束以动态方式合并到适应度函数中，形成一个具有变化的带惩罚项的适应度函数。

选择。本文采用精英保留锦标赛选择。

重复选择、交叉、变异的过程，逐步迭代，直到取得最优解时停止。

1.2 适应度函数

关于约束条件的限制，我们主要是通过适应度函数来进行筛选。在进行适应度函数的设计时，重点考虑以下几种约束条件：①如果不符合约束条件，则赋予适应度函数较小的数值;②如果在交叉过程中，出现了相同的基因，则适应度函数值约束为0;③如果选定一个组合后，该组合在某一个指标上都很弱，则予以将其剔除。

2  供应商选择的实例分析

本文以从5个供应商中选择3个的最优组合为案例进行实证分析。专家经过讨论得出了评价供应商的三个重要指标：质量、交货期、成本。指标权重的确定采用AHP方法得出。从表1中可以得出供应商5在交货期的得分很高，但其在质量和成本方面的得分比较弱。供应商2在质量属性上的得分较高，而其在成本和交货期方面得分较低。所以在选择供应商时具有以下的几个约束条件的限制：供应商合作伙伴整体最优，同时能够达到一种优势互补的效果;如果某一个供应商在某一个指标上的得分很低，则赋予其惩罚约束;如果M个供应商在某一个指标上都很弱，则不予选择这个组合。评价得分表如表1所示。

接下来，分别采用线性加权法（方法一）、？姿截集标准化矩阵法（方法二）和本文提出的改进的遗传算法（方法三）进行计算。其综合结果如表2所示。

针对本文提出的改进的遗传算法，其相关遗传算子的设计为：初始种群为20，交叉的概率为0.6，变异的概率为0.01，终止迭代的次数为1000。L的取值为L=（6，5，4.3）T。

三种计算的结果并不完全一致。通过分析，进一步得出：

方法一属于简单的线性加权，并未考虑到约束条件的限制，是理想状态。该方法适用于从众多的方案中选择一个最优解的情况，并不适用于组合优化问题的解决。

方法二通过对低于给定的的值赋予0的惩罚项，容易造成信息的失真，并不能达到优势互补的效果。

方法三則很好的弥补了上面两种方法的不足，通过对适应度函数的设计，将不满足约束条件的组合通过适应度函数予以筛选，从而得到了最优的结果，很好的解决了本文提出的问题。

3  结论

本文通过对遗传算法中编码和适应度函数的设计，将约束条件通过适应度函数来体现，有效的解决了从N个候选方案中选择M个的最优组合优化问题。同时本文将线性加权法、？姿截集标准化矩阵法与本文提出的方法进行了对比。结果发现：本文提出的改进的遗传算法在解决约束条件下的组合优化问题方面更优，更符合现实意义，从而验证了算法的有效性。

参考文献：

[1]苑立伟，等.改进遗传算法及其在背包问题中的应用[J].系统工程与电子技术，2005，27.

[2]张大斌，等.基于群体编码方式的遗传算法求解装箱问题[J].计算机工程与设计，2008，29.

[3]贺永兴，杨瑞，唐伟，欧新良.基于重构变异算子遗传算法的研究[J].计算机技术与发展，2015，25.

[4]王翯华，朱建军，姜方桃.供应链协同视角下我们大型客机供应商选择评价指标设计[J].价值工程，2015，12.