机器学习-遗传法.ppt

第9章 遗传算法 9.2.1 表示假设 表示假设 遗传算法中的假设常常被表示成二进制位串，这便于用变异和交叉遗传算子来操作。 把If-then规则编码成位串： 1.首先考虑使用位串描述单个属性的值约束 表示假设 例如考虑属性Outlook，它的值可以为以下3个值中的任何一个：Sunny、Overcast或Rain。 表示Outlook约束的一个明显的方法是，使用一个长度为3的位串，每位对应一个可能值。某位为1，表示这个属性可以取对应的值。例如，串010表示Outlook=Overcast；类似的，串011表示Outlook可以取两个值，即(Outlook=Overcast∨Rain)。 注意：串111表示最一般的约束，(Outlook=Sunny∨Overcast∨Rain) 表示假设 2.多个属性约束的合取可以很容易地表示为对应位串的连接 例如考虑第二个属性Wind，可以取两个值Strong或Weak。 那么下面的规则前件： （Outlook=Overcast∨Rain）∧(Wind=Strong) 可被表示为长度为5的位串： Outlook Wind 011 10 规则的后件也可以用相似的方式表示，如PlayTennis=yes可以表示为串10 表示假设 3.整个规则表示可以通过把描述规则前件和后件的位串连接起来 例如规则： IF Wind=Strong THEN PlayTennis=yes 将被表示为以下位串： Outlook Wind PlayTennis 111 10 10 表示假设 位串的特点： 表示规则的位串对假设空间中的每个属性必须有一个子串，即使该属性不被规则的前件约束。 得到一个固定长度的规则位串表示，其中特定位置的子串描述对应特定属性的约束。 规则集的表示：单个规则的位串表示连接起来。 表示假设 在为某个假设空间设计位串编码是，有必要让每个句法合法的位串表示一个有意义的假设。 比如，位串111 10 11表示一个规则，它的后件不约束目标属性PlayTennis。 如果要避免考虑这个假设，可以采用不同的编码方式（例如，仅分配一个位给后件PlayTennis，表示它的值是Yes或No），或者改变遗传算子以明确避免建立这样的位串，或把很低的适应度赋给这样的串。 假设也可以用符号描述来表示，而不是位串，比如计算机程序。 * * *