基于分解-并行遗传算法的约束优化算法

摘要

本发明公开了一种基于分解‑并行遗传算法的约束优化算法，将约束优化算法所针对的问题分解成Q个子问题和1个常规问题，先采用遗传算法分解得到的Q个子问题并行进行迭代进化，直到每个子问题所对应的种群中至少有一半以上的染色体满足该子问题的约束条件，从子问题中选择满足约束条件的染色体按顺序组成多条染色体，作为常规种群的初始种群；然后对常规问题和子问题进行并行遗传算法迭代，达到迁移间隔时即分别进行前向迁移和后向迁移，当迁移次数达到阈值，从常规问题的种群中选择最优染色体作为约束优化问题的解。本发明采用分解‑并行遗传算法，可以快速求解出约束优化问题的最佳或近优解。

主权项

一种基于分解‑并行遗传算法的约束优化算法，其特征在于，包括以下步骤：S1：将约束优化算法所针对的问题分解成Q个子问题和1个常规问题，其中Q个子问题所对应的决策变量子集和约束条件子集均不存在重叠，常规问题包含所有决策变量和除Q个子问题约束条件子集以外的其他约束条件；S2：采用遗传算法对步骤S1分解得到的Q个子问题并行进行迭代进化，直到每个子问题所对应的种群中至少有一半以上的染色体满足该子问题的约束条件；S3：分别从当前每个子问题的种群中满足该子问题约束条件的染色体中随机选择若干个个体，将来自不同子种群中的染色体按照子问题顺序依次组合起来，构成多条染色体，作为常规种群的初始种群；S4：令进化代数t＝1；S5：采用遗传算法对Q个子问题和常规问题分别进行一次迭代进化，其中常规问题的迭代进化中，交叉操作时，个体的交叉点只能为常规染色体中对应子问题染色体的起始点，并且常规问题的染色体不进行变异操作；S6：如果t％A＝0，其中A表示种群迁移间隔，％表示求余运算，则进入步骤S7，否则令t＝t+1，返回步骤S5；S7：各自从常规问题和每个子问题的当代种群中随机选择N个满足约束条件的染色体作为被迁移染色体；将常规问题的N个被迁移染色体按照子问题进行分段，共分为Q×N段，用每个子问题所对应的N个染色体段对该子问题种群中的N个被迁移染色体进行覆盖；将来自于Q个子问题的Q×N个被迁移染色体按照子问题顺序组合成N个常规问题染色体，子问题中的每个被迁移染色体在组合时只使用一次，然后将组合得到的N个常规问题染色体去补全常规种群中之前被迁移走的N个染色体；S8：如果t/A＜T，令t＝t+1，返回步骤S5，否则从常规问题的种群中选择最优染色体作为约束优化问题的解。