基于复杂适应度函数的因素遗传算法

2020-04-09钟育彬邓文杰

广州大学学报（自然科学版） 2020年5期

钟育彬, 邓文杰

(广州大学数学与信息科学学院, 广东广州 510006)

在目标约束函数寻优领域中，目前已经有多种寻优算法，如鱼群算法、蚁群算法、粒子群算法和遗传算法等.其中,遗传算法是最为“万金油”的寻优算法，只要从问题中归纳出目标函数与约束条件，便能进行运算得出结果.但针对复杂适应度函数的运算速率往往引人诟病[1].遗传算法是模拟达尔文生物进化论的自然选择“物竞天择，适者生存”，以染色体为媒介，通过交叉、变异产生新个体，然后不断选择优良个体的寻优算法[2].它最初由Holland[3]于1975年首先提出.经过多年的发展，遗传算法已十分成熟.

本文为在改进交叉选择的前提下，保证遗传算法尽可能不陷入局部最优的情况而选择综合多种群遗传算法.相对于普通遗传算法，多种群遗传算法[4]首先将多个个体放于若干遗传种群中，各种群通过不同的控制参数调节，由各移民算子进行联系，然后比较每代各种群的最优解而获得当代最优染色体，实现了多个种群共存进化的效果，从而有效避免了遗传算法的运算陷入局部最优.

1 针对复杂适应度函数遗传算法存在的问题

普通适应度函数是指遗传机理框架中仅需放入目标函数与约束条件的适应度函数.无论在算法效率或者结果，遗传算法应用在普通适应度函数上都有满意的效果.

复杂适应度函数是指实际任务所需要求得的某些未知数xi,不直接呈现于目标函数，而对未知数进行数据量较大的若干计算、判断，甚至进行内含计算算子运算等操作，最终反作用于目标函数.在需要寻优的日常生活问题或数学建模竞赛中，这类复杂适应度函数出现频率不低.在2016年的广东省金融数学建模竞赛中，要用遗传算法获得金融K值，就要对所需求得的未知数xi进行极大的数据运算，方能放入目标函数中求值.

假设遗传代数为n，交叉产生新个体的数目为p，运算单次复杂适应度函数的时间花费为t，遗传算法完成所需的时间T.每进行一次遗传机理框架的计算需要进行p次的适应度函数计算，总需执行n代,则

T=n·p·t.

设运行一次复杂适应度函数所需时间为1 s，一般设置遗传100代，每代生成200个体.则需要333.3 min运算出结果.某些复杂适应度函数计算所需时间大于1 s，需计算机长时间运算.

为尽快提高遗传算法的收敛速度且保证算法不陷入局部最优，本文提出针对复杂适应度函数的因素遗传算法.

2 基于复杂适应度函数的因素遗传算法

遗传算法的进化究其根本在于染色体进化，染色体的进化在其编码长度与对应位置的数值进化，亦是交叉变异的内涵[5].由于二进制编码中每一代对应位置的数值在0,1间变化，则染色体编码位置构造对染色体进化起着决定性作用.因素空间理论中成熟的模糊评价体系[6-7]能更有效地提取遗传性更强个体.本文根据遗传算法进化本质提出因素遗传算法

定义1 (相似数)设遗传算法的两个编码集为{A1,A2,…An}，{B1,B2,…Bn},则其对应位置的相似数记为

ci=|Ai-Bi| (i=1,2…n).

定义2 (相似度)因为遗传编码多样，需要对相似集进行归一化处理，其相似度记为

定义3(贴近度)下文方法需要设计遗传性质更优的染色体，其内含位置及染色体长度不仅要尽可能地与最优适应度最相似，且与最差染色体最不相似，则定义其贴近度为

步骤1编码

编码的方式有二进制编码、格雷码法、符号编码法等.复杂适应度函数一般具有其复杂问题背景.符号编码法符合有意义积木块编码原则，适合解决针对性问题且容易与其他相关算法混合使用.故本文以符号编码法为例，建立代码符号集{A,B,C…}.二进制编码法只需进行位置划分同样可达本文效果[8].

步骤2选择

确定符号集为因素集{A1,A2,…Ai}，设预选比较进化参数为j，用以下方法选择最大适应度染色体X.

其中，X为最大适应度染色体，f为当代进入遗传机理框架运算的染色体，n为当代进入遗传机理框架运算的染色体个数.

同理，取最小适应度染色体与适应度排名前j个的染色体，对选中染色体进行贴近度计算，获得贴近度度矩阵R.

最后，根据最大隶属度原则[9]，构建每个划分位置最优的最佳遗传性质染色体Q.

步骤3交叉

遗传算法适用交叉算子有pmx、pbx、obx、cxo等，针对不同的问题背景可自行选择合适的交叉算子.遗传机理进入交叉过程时，将适应度最优染色体X与最佳遗传性质染色体Q代入.

步骤4变异

亦然，将适应度最优染色体X与染色体Q代入变异过程，设定变异概率产生新个体[10].

步骤5循环迭代

重复进行步骤2-4，直到遗传代数达到预设代数后，算法终止.

3 算法时间复杂度分析

对一个当代预选比较进化参数为m，染色编码长度划分为n的因素遗传算法，分别计算m个染色体与当代最优、最差染色体的相似数计算量为2mn.作m次归一化处理，求贴近度计算量为m.再作nm次比较获得全新染色体.故本文改进点的计算量为

T=3mn+2m.

本文加入的算法时间复杂度为o(n2)，即相对普通MPGA,其适应度函数内除标准目标函数与约束条件框架外，还有计算量大于上式的程序操作，可选用本文方法进行操作.

4 实例分析

本文以基于混合堆叠模型的广告转化率预测[11]为例.数据来源为2018年天池算法竞赛“阿里妈妈搜索广告转化预测”.由于原始数据特征偏少、稠密且复杂，LightBGM和XGBoost的预测效果远优于其他预测模型，且对数损失(Logloss)值低于wide_deep 和 wide_cross 神经网络模型.混合融合模型的思想是混合与堆叠.LightBGM堆叠XGBoost是指将部分数据放入LightBGM训练得到新的特征组放入原始数列放入到XGBoost进行预测，混合是指不同预测模型所得到的结果加权平均处理，该权重的选取会对最终预测结果产生直接影响.寻优思想解决权重选取问题，以对数损失最少作目标函数，建立寻优模型如下：

其中，N为样本总数，yi是0，1变量，表示第i个样本的label,pi为模型预测第i个样本label为1的概率，xi为混合模型权重取值,Q为混合模型，modle1为LightBGM，modle2为XGBoost堆叠LightBGM，modle3为LightBGM堆叠XGBoost.

固定LightBGM和XGBoost的参数设置，比较多种群遗传算法与基于因素空间的多种群遗传算法.由于本文着重比较权重选取寻优算法，故只提出部分参数取值，其他未提及的参数皆取默认值.其中，两个树模型的部分参数选取见表1及表2.