本场景使用的遗传算法编码技术
Genetic algorithm encoding technique to be used in this scenario
问题是用遗传算法在多个仓库中找到总成本最低的最佳数量。
假设有 n 个仓库。与每个仓库相关联的有几个因素：
- LCosti: 仓库i的装载成本
- HCosti: 仓库 i
的持有成本
- TCosti: 仓库i的运输成本
- OCosti: 仓库 i
的订购成本
每个仓库都有与其关联的数量 Qi，必须满足这 4 个条件：
- 装载约束：Qi * LCosti >= Ai for 仓库 i
- holding constraint: Qi * HCosti >= Bi 仓库i
- 运输约束：Qi * TCosti >= Ci 仓库 i
- 排序约束：Qi * OCosti >= Di 对于仓库 i
其中 A、B、C 和 D 是每个仓库的常量。
还有一个重要的标准就是每个Qi必须满足：
- Di>=Qi
其中 Di 是仓库 i 的需求。
总成本方程为：
Total cost = sum(Qi * (LCosti + HCosti + TCosti) + OCosti / Qi)
如何为这个问题编码染色体？我在想的是，结合给出 Qi 的最小允许值的四个约束之一和最后一个约束，我可以获得 Qi[ 的范围=63=]。然后我可以为初始群体随机生成该范围内的值。但是在上述场景中如何进行交叉和变异呢？我如何编码染色体？
一般来说，在约束问题中，你基本上有三种可能的方法（关于进化算法）：
1。将约束违规纳入适应度
您可以将您的适应度设计为实际 objective 和违反约束的惩罚之和。极端情况是 "death penalty"，即任何以任何方式违反任何约束的个体都会获得最差的适应度。
这种方法通常很容易实现，但是有一个很大的缺点：它通常会惩罚具有良好构建块但过多违反约束的解决方案。
2。纠错算子，抗性编码
如果您的问题可行，您可以实施 "correction operators" - 运算符采用违反约束的解决方案并将其转换为另一个不违反约束的解决方案，同时尽可能多地保留原始结构尽可能解决。类似的事情是使用这样一种编码，保证解决方案总是可行的，即你有这样一个总是产生有效解决方案的解码算法。
如果可能的话，这可能是您可以采用的最佳方法。但是，通常很难实施，或者如果不对解决方案进行重大更改就无法实施，这会大大减慢搜索速度，甚至使其无用。
3。多objective方法
使用一些多objective (MO) 算法，例如NSGA-II，并将您的约束违规度量转换为 objectives 并立即优化所有 objectives。 MO 算法通常提供 pareto-front 解决方案 - 一组位于 objective-violation tradeoff space.
前沿的解决方案
使用 Differential Evolution 可以保持相同的表示并避免双重转换（整数 -> 二进制，二进制 -> 整数）。
变异操作为：
V(g+1, i) = X(g, r1) + F ⋅ (X(g, r2) − X(g, r3))
其中：
i、r1、r2、r3是种群中向量的引用，none等于另一个- F 是 [0, 1.5] 范围内的随机常数
V（突变向量）与目标向量（X(g, i)）的元素重组构建一个 试验向量 u(g+1, i)。选择过程从试验向量和目标向量中选择更好的候选者（有关详细信息，请参阅下面的参考资料）。
这种方法有趣的方面是：
- 您没有重新设计代码。您需要一个不同的突变/重组运算符，并且（也许）您必须将一些实数转换为整数，但它既简单又快速；
- 对于约束管理，您可以采用
回答中描述的技术；
- DE 已被证明对大范围的优化问题有效，它似乎适合您的问题。
参考文献：
- Explain the Differential Evolution method and an old Dr.Dobb's article（作者：Kenneth Price 和 Rainer Storn）作为介绍；
- Storn's page 了解更多详细信息和许多代码示例。
问题是用遗传算法在多个仓库中找到总成本最低的最佳数量。
假设有 n 个仓库。与每个仓库相关联的有几个因素：
- LCosti: 仓库i的装载成本
- HCosti: 仓库 i 的持有成本
- TCosti: 仓库i的运输成本
- OCosti: 仓库 i 的订购成本
每个仓库都有与其关联的数量 Qi，必须满足这 4 个条件：
- 装载约束：Qi * LCosti >= Ai for 仓库 i
- holding constraint: Qi * HCosti >= Bi 仓库i
- 运输约束：Qi * TCosti >= Ci 仓库 i
- 排序约束：Qi * OCosti >= Di 对于仓库 i
其中 A、B、C 和 D 是每个仓库的常量。
还有一个重要的标准就是每个Qi必须满足：
- Di>=Qi
其中 Di 是仓库 i 的需求。
总成本方程为：
Total cost = sum(Qi * (LCosti + HCosti + TCosti) + OCosti / Qi)
如何为这个问题编码染色体？我在想的是，结合给出 Qi 的最小允许值的四个约束之一和最后一个约束，我可以获得 Qi[ 的范围=63=]。然后我可以为初始群体随机生成该范围内的值。但是在上述场景中如何进行交叉和变异呢？我如何编码染色体？
一般来说，在约束问题中，你基本上有三种可能的方法（关于进化算法）：
1。将约束违规纳入适应度
您可以将您的适应度设计为实际 objective 和违反约束的惩罚之和。极端情况是 "death penalty"，即任何以任何方式违反任何约束的个体都会获得最差的适应度。
这种方法通常很容易实现，但是有一个很大的缺点：它通常会惩罚具有良好构建块但过多违反约束的解决方案。
2。纠错算子，抗性编码
如果您的问题可行，您可以实施 "correction operators" - 运算符采用违反约束的解决方案并将其转换为另一个不违反约束的解决方案，同时尽可能多地保留原始结构尽可能解决。类似的事情是使用这样一种编码，保证解决方案总是可行的，即你有这样一个总是产生有效解决方案的解码算法。
如果可能的话，这可能是您可以采用的最佳方法。但是，通常很难实施，或者如果不对解决方案进行重大更改就无法实施，这会大大减慢搜索速度，甚至使其无用。
3。多objective方法
使用一些多objective (MO) 算法，例如NSGA-II，并将您的约束违规度量转换为 objectives 并立即优化所有 objectives。 MO 算法通常提供 pareto-front 解决方案 - 一组位于 objective-violation tradeoff space.
前沿的解决方案使用 Differential Evolution 可以保持相同的表示并避免双重转换（整数 -> 二进制，二进制 -> 整数）。
变异操作为：
V(g+1, i) = X(g, r1) + F ⋅ (X(g, r2) − X(g, r3))
其中：
i、r1、r2、r3是种群中向量的引用，none等于另一个- F 是 [0, 1.5] 范围内的随机常数
V（突变向量）与目标向量（X(g, i)）的元素重组构建一个 试验向量 u(g+1, i)。选择过程从试验向量和目标向量中选择更好的候选者（有关详细信息，请参阅下面的参考资料）。
这种方法有趣的方面是：
- 您没有重新设计代码。您需要一个不同的突变/重组运算符，并且（也许）您必须将一些实数转换为整数，但它既简单又快速；
- 对于约束管理，您可以采用
- DE 已被证明对大范围的优化问题有效，它似乎适合您的问题。
参考文献：
- Explain the Differential Evolution method and an old Dr.Dobb's article（作者：Kenneth Price 和 Rainer Storn）作为介绍；
- Storn's page 了解更多详细信息和许多代码示例。