此方案中将使用的遗传算法编码技术 [英] Genetic algorithm encoding technique to be used in this scenario

问题描述

问题是使用遗传算法找到在一定数量的仓库中产生最低总成本的最优数量。

The problem is to find the optimum quantity that incurs minimum total cost in a number of warehouses using genetic algorithm.

假设有 n 个仓库。与每个仓库相关的一些因素：

Let's say there are n warehouses. Associated with each warehouse are a few factors:

• LCost _i ：仓库i的装载成本


• HCost _i ：仓库i的持有成本


• TCost _i ：仓库i的运输成本


• OCost _i ：仓库i的订购成本

• LCost_i: loading cost for warehouse i
• HCost_i: holding cost for warehouse i
• TCost_i: transportation cost for warehouse i
• OCost_i: ordering cost for warehouse i

每个仓库都有必须满足以下4个条件的与之关联的数量Q _i ：

Each warehouse has quantity Q_i associated with it that must satisfy these 4 criteria:

• 加载约束：Q _i * LCost _i > = A _i 仓库i


• 持有约束：Q _i * HCost _i > = B _i 用于仓库i


• 运输约束：Q _i * TCost _i > = C _i 用于仓库i


• 订购约束：Q _i * OCost _i > = D _i 用于仓库i

• loading constraint: Q_i * LCost_i >= A_i for warehouse i
• holding constraint: Q_i * HCost_i >= B_i for warehouse i
• Transportation constraint: Q_i * TCost_i >= C_i for warehouse i
• Ordering constraint: Q_i * OCost_i >= D_i for warehouse i

其中A，B，C和D是每个仓库的常数。

where A, B, C and D are constants for each of the warehouses.

另一个重要标准是每个Q _i 必须满足：

Another important criterion is that each Q_i must satisfy:

• D _i > = Q _i

• D_i >= Q_i

其中D _i 是需求

总成本的等式是：

总计成本= sum（Q _i *（LCost _i + HCost _i + TCost _i ）+ OCost _i / Q _i ）

Total cost = sum(Q_i * (LCost_i + HCost_i + TCost_i) + OCost_i / Q_i)

如何为这个问题编码染色体？我在想的是，结合给出Q _i 的最小允许值的四个约束之一和最后一个约束，我可以获得Q _i 的范围。然后，我可以为初始总体随机生成该范围内的值。但是在上述情况下如何执行交叉和变异？我该如何编码染色体？

How do I encode a chromosome for this problem? What I am thinking is that combining one of the four constraints that gives a minimum allowable value for Q_i and the last constraint, I can get a range for Q_i. Then I can randomly generate values in that range for the initial population. But how do I perform crossover, and mutation in the above scenario? How do I encode the chromosomes?

推荐答案

通常，在受约束的问题中，您基本上有三种可能的方法（关于进化算法）：

Generally, in constrained problems you have basically three possible approaches (regarding evolutionary algorithms):

您可以将适应度设计为实际目标与违反约束的惩罚之和。极端的情况是死刑，即任何以任何方式违反任何约束的个人都将遭受最坏的适应。

You can design your fitness as a sum of the actual objective and penalties for violation of constraints. The extreme case is a "death penalty", i.e. any individual which violates any constraint in any way receives the worst possible fitness.

这种方法通常很容易实现，但是但是，它有一个很大的缺点：通常会惩罚具有良好构建基块但过度违反约束的解决方案。

This approach is usually very easy to implement but, however, has a big drawback: it often penalizes solutions that have good building blocks but violate the constraints too much.

如果可能出现问题，则可以实现校正运算符-采取违反约束并将其转换为另一种解决方案的运算符不会违反约束，因此保留了原始解决方案中尽可能多的结构。类似的事情是使用保证这样的编码，使该解决方案始终可行，即您具有始终可产生有效解决方案的解码算法。

If it is possible for your problem, you can implement "correction operators" - operators that take a solution that violate constraints and transform it into another one that does not violate the constraints, preserving as much structure from the original solution as possible. Similar thing is to use such an encoding that guarantees that the solution will always be feasible, i.e. you have such a decoding algorithm that always produces valid solution.

如果可能，这可能是您可以采取的最佳方法。但是，通常很难实施，或者如果不对解决方案进行重大更改就无法实现，这可能会大大降低搜索速度，甚至使其变得毫无用处。

If it is possible, this is probably the best approach you can take. However, it is often quite hard to implement, or not possible without major changes in the solutions which can then significantly slow the search down, or even make it useless.

使用一些多目标（MO）算法，例如NSGA-II，并将您违反约束的措施转变为目标并立即优化所有目标。 MO算法通常提供解决方案的先验条件-一套在客观违规权衡空间前面的解决方案。

Use some multi-objective (MO) algorithm, e.g. NSGA-II, and turn your measure(s) of constraint violation into objectives and optimize all the objectives at once. The MO algorithms usually provide a pareto-front of solutions - a set of solutions that are on the front of the objective-violation tradeoff space.

这篇关于此方案中将使用的遗传算法编码技术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！