针对遗传算法在最大子团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷，利用随机抽样方法对交叉操作进行重新设计，结合免疫机理定义染色体浓度，设计克隆选择策略，提出了求解最大子团问题的随机抽样免疫遗传算法。用仿真算例说明了新算法在解的质量、收敛速度等各项指标上均有提高，且不比DLS-MC、QUALEX等经典搜索算法差，对某些算例还得到了更好解。