遗传算法编码

Question

我正在尝试创建一个算法，我认为它类似于背包问题。问题是找到某些中间产品的配方/材料清单。中间产品的配方有不同的选择。例如，产品X可以包括25 %的原料A+ 75 %的原料B，或50 %的原料A+ 50 %的原料B，等等。每个配方有1到100种不同的选择。

我的问题是，如何最好地编码不同的配方选择(和/或在互联网上发现类似的问题)。我认为我必须使用值编码(为食谱中的每一个选项指定一个值)。我有合理的，不同的选择吗？

谢谢和亲切的问候

Answer 1

你可以用一个数字染色体来编码这个问题。如果你的产品含有N种成分，那么你的数字染色体的长度是N: X={x1，x2，.，xN}。染色体上的每一个数字xi代表成分i的部分，不需要将数字相加为1。例如，X={ 23 ,5,0}指的是，你需要23份成分1，5份成分2和0份成分3。

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

Answer 2

您可以使用一个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;