遗传算法能否有效优化求解该类NP完全的最大子群查找问题？

你要找的满足「内部所有元素两两比较返回true」的最大子群，本质是无向图中的最大团：把数组每个元素映射为图的顶点，两个顶点之间连边当且仅当对应两个元素的比较结果为true，你的需求完全等价于在这个图里找顶点数最多的完全子图。
这个问题是经典的NP难问题，不存在多项式时间的精确解法，你提到的N!量级穷举完全不具备可行性是正常的；你之前尝试的随机逐次添加元素的方案属于最朴素的随机贪心策略，极易陷入局部最优，最终得到的子群规模偏小是这类方法的通病。

遗传算法完全可以用于求解这个问题，只要针对问题特性做适配设计，完全可以在合理时间内得到比随机贪心方案规模大得多的近优解，但要明确它是启发式算法，不保证能找到全局最优的绝对最大子群。
如果要落地用遗传算法求解，别直接套通用框架，按下面的要点设计效率和结果质量会高很多：

• 编码直接用长度为N的0-1二进制串即可，第i位为1代表选中数组第i个元素进入子群，为0代表不选，没有必要搞复杂编码。
• 适应度函数要同时考虑规模和合法性：基础得分设为当前选中的元素数量，每发现一对选中元素的比较结果为false就扣除高额惩罚分（比如每对扣2分以上），确保高适应度的个体首先是满足两两比较要求的合法子群，其次才是规模尽可能大。
• 遗传算子选最稳妥的组合即可：选择用锦标赛选择，比轮盘赌更不容易过早收敛；交叉用单点交叉或者均匀交叉都可以；变异就用随机位翻转，变异率控制在0.1%~1%区间调整即可。
• 一定要加局部优化步骤，这是效果提升的核心：每次交叉、变异生成新个体后后，先做合法性修复——如果当前选中的集合存在不满足比较要求的冲突对，就随机删掉冲突对中的一个元素，直到集合变成合法的团；之后再做贪心扩张——遍历所有未选中的元素，只要某个元素和当前合法团里的所有元素比较都为true，就把它加进团里。加完这两步，收敛速度和最终解的质量会比纯遗传算法高几个档次。

如果不想花时间调遗传算法的参数，也可以选下面这些更成熟的方案，很多时候投入产出比更高：

• 如果你的比较函数满足传递性（即a与b比较为true、b与c比较为true时，a与c比较一定为true），那这个问题根本不需要复杂算法，直接用并查集就能在接近O(N)的时间复杂度下算出所有等价类，最大的等价类就是你要的结果。
• 针对最大团问题有成熟的带剪枝的精确算法，比如Bron–Kerbosch算法加分支定界剪枝，在N规模为几千以内的场景下甚至能直接跑出全局最优的最大团，规模更大的时候加启发式剪枝，结果质量也不逊于调参一般的遗传算法。
• 你之前用的随机贪心可以做个小改进，效果就能提升很多：多跑几百上千轮，每轮随机选起点之后，每次添加元素不要随便挑一个匹配的，而是优先选「和当前团内所有元素匹配、同时和剩余未选元素匹配数最高」的元素加入，所有轮次跑完取规模最大的合法子群即可，这个方案实现代码量极小，很多时候效果比没加局部优化的纯遗传算法还好。

内容的提问来源于stack exchange，提问作者blackpill