摘要：
近期，安徽大学、东北大学和西湖大学的研究人员提出了一种基于神经网络的降维思想用于求解超大规模二进制优化问题。基于该思想设计了一种简洁的神经网络降维方法，建立了从问题数据集到单个解的映射关系。通过调整神经网络的权值便可更改输出的解，从而将大规模二进制变量的优化任务转换为小规模连续权值的优化任务。实验证实，包含二十余个权值的全连接神经网络消耗一万次函数评价便能有效求解高达一千万变量的二进制优化问题。该方法无需训练神经网络、无需先验知识、无需梯度信息，对目标函数的形式和数目没有要求。
论文地址：https://ieeexplore.ieee.org/document/10530207
代码地址：https://github.com/BIMK/PlatEMO
科学问题：
二进制优化问题指决策变量取值为0或1的优化问题，其广泛存在于各领域（如智慧物流、推荐系统、网络科学、故障诊断等）中。现有二进制优化方法主要包括数学规划方法（将二进制变量转换为实数变量）、元启发式方法（交叉变异直接搜索）和神经网络方法（模型输出问题的解）。然而，这些方法在大规模二进制优化问题上面临收敛速度慢、计算代价高等困境。为此，本文提出了一种基于神经网络的降维思想，旨在将大规模二进制优化问题转换为小规模连续优化问题，并用普通遗传算法求解。
研究现状：
神经网络已被广泛用于求解二进制优化问题，主要思想有代理模型、搜索空间降维、有监督学习、强化学习、变量转换等。在面临大规模二进制优化问题时，由于变量过多、样本过少，代理模型方法难以准确拟合大规模变量和目标函数之间的映射关系，搜索空间降维方法难以准确学习最优子空间，有监督学习方法难以获取最优解作为训练样本，强化学习方法面临过于庞大的动作空间，变量转换方法需要优化数量过多的神经网络权值。因此，本文提出了一种全新的神经网络降维思想，克服变量过多、样本过少的难题。
（图标题）代理模型方法
（图标题）搜索空间降维方法
（图标题）有监督学习方法
（图标题）强化学习方法
（图标题）变量转换方法
方法简介：
（图标题）本文方法
本文方法使用了单个全连接神经网络，其输入是单个决策变量所对应物品的特征，输出是该二进制决策变量，即表示该物品是否被选择。可见该神经网络的规模与变量或物品数目无关，因此可解决变量过多的难题。另一方面，调整该神经网络的权值便可改变输出的决策变量，因此可将大规模二进制变量的优化任务转换为小规模连续权值的优化任务。可见该神经网络无需任何训练，因此可解决样本过少的难题。
（图标题）本文方法的流程
基于以上思想，本文提出了一种简洁的神经网络降维方法。该方法建立了从问题数据集到单个解的映射关系，并利用遗传算法优化神经网络的权值来改变其输出的解。得益于遗传算法的高通用性，该方法可优化任意形式和数目的黑盒目标函数，无需函数的梯度信息。
对于非图问题，一般可直接获取每个物品的特征，如背包问题中物品的价值和重量、实例选择问题中样本的固有特征等。为更好地区分特征相近的物品，本文方法为每个物品的特征添加了随机扰动。对于图问题，一般仅有该图的邻接矩阵信息，因此本文设计了基于谱聚类的节点特征提取方法，使全连接神经网络具备和图卷积网络类似的图学习能力。
由于该神经网络仅输入单个物品的特征，本文方法使用了仅具有4个神经元的单隐层神经网络，具有非常高的计算效率。实验表明，该神经网络具有与更复杂的全连接神经网络、循环神经网络和图卷积网络类似的性能。
实验结果：
（图标题）本文方法NNDREA与其他方法在大规模问题上的HV值对比
本文方法与12个启发式方法、元启发式方法（包括稀疏进化算法）和神经网络方法（包括强化学习方法）在背包问题、最大割问题、多目标背包问题、实例选择问题、社团检测问题和关键点识别问题上进行了性能对比。结果表明，本文方法具有显著更好的优化性能。
（图标题）本文方法NNDREA与其他方法在超大规模问题上的HV值和运行时间对比
同时，在具有一千万变量的多目标背包问题上，当函数评价次数为一万时，本文方法仍具有显著的性能和效率优势。在该规模问题上，一些现有算法已无法成功运行。
未来工作：
本文提出了一种求解超大规模二进制优化问题的神经网络降维思想，证实了极为简单的全连接神经网络也能带来较好的优化效果。在未来，可研究使用更复杂的神经网络以求解更复杂的组合优化问题。在神经网络的输入层面，实现从复杂数据集中自动提取合适的物品特征，从而求解物品特征不明确的优化问题（如频繁模式挖掘）。在神经网络的输出层面，实现输出序列变量而非二进制变量，从而求解序列优化问题（如车辆路径问题）。
最后，欢迎转载，欢迎留言，欢迎扔砖，欢迎吐槽，欢迎提问，还有欢迎关注（长按下面二维码识别）。
