遗传算法编码

Question

我正在尝试创建一个我认为类似于背包问题的算法。问题是为某些中间产品找到 recipes/Bill-of-Materials。中间产品有不同的配方可供选择。例如，产品 X 可以包含 25% raw material A + 75% raw material B，或 50% raw material A + 50% raw material B，等等。每个食谱有 1 到 100 种不同的选择。

我的问题是，如何最好地对不同的食谱备选方案进行编码（and/or 在互联网上哪里可以找到类似的问题）。我想我必须使用值编码，即为食谱的每个备选方案分配一个值。我有合理的、不同的选择吗？

谢谢和亲切的问候

Answer 1

您可以使用 100 个维度变量来呈现一个人，如下所示

X={x1,x2,x3,...,x100} xi∈[0,1] ∑(xi)=1.0

很难用交叉operation.So我建议只能通过变异操作产生后代

对父个体的变异操作'X':

(1)randly choose two dimention 'xi' and 'xj' from 'X';

(2)p=rand(0,1);

(3)xj=xj+(1-p)*xi;

(4)xi=xi*p;

Answer 2

你可以用数字染色体对问题进行编码。如果您的产品含有 N 种成分，那么您的染色体数的长度为 N: X={x1,x2,..,xN}。染色体的每一个数字xi代表成分i的部分。不需要数字总和为一。例如。 X={23,5,0} 表示，您需要 23 份成分 1、5 份成分 2 和零份成分 3。

使用这种编码，交叉不会使染色体失效。

遗传算法编码

Genetic-algorithm encoding

encoding

knapsack-problem

genetic-algorithm