IEEE Computational Intelligence Magazine - August 2020 - 34

Particularly for BioHEL, three characteristics were considered to classify the problems:
❏ The number of negative examples in the problem (defined
in section 5.1.1).
❏ The number of good individuals in a random sample after
evaluating them against the given problem. These are individuals that do not make classification mistakes or that have
an accuracy higher than a certain threshold (defined in section 5.1.2).
❏ The number of attributes expressed in the good individuals
(defined in section 5.1.3).
The following sections will explain in greater detail each one of
the criteria used to classify the problems (section 5.1). Afterwards, we
will show in more detail how the kr-space is partitioned in kr-groups
and what makes a problem belong to a specific group (section 5.2).
Finally, we explain the algorithm step-by-step (section 5.3).
5.1. Classification Criteria

This section explains each one of the criteria used within BioHEL to classify the problems: a) the number of negative examples in the problem, b) the number of good individuals in a
random sample after evaluating them against the given problem
and c) the number of attributes expressed in the good individuals. The first two characteristics used are completely theorydriven, which means they use theoretical models to determine
the kind of problem we are handling. The last characteristic,
even though it does not come from a model, reinforces the two
previous criteria in finding the correct kr-group. Since the good
individuals are already calculated for the second criterion, using
the number of attributes expressed in these individuals does not
involve an extra computational cost.
5.1.1. Number of Negative Examples in the Problem
Depending on the number of terms r and number of attributes
expressed in each term k, the k-DNF problem will present a
different percentage of negative examples.
For a randomly generated binary problem defined as the
disjunction of r terms, where each term is the conjunction of k
randomly picked attributes, the probability of having a negative
example in the training set P (neg) kr is equal to Equation (4)
shown in Section 4.
By counting the number of negative examples in the training
set, it is possible to use this formula inversely to determine possible combinations of k and r that are feasible for the given problem. For example a problem with k = 2 and r = 1 has 75% of
negative examples. But also a problem with k = 6 and r = 18 has
on average the same percentage of negative examples. If we
observe a particular problem with 75% of negative examples both
of these kr-groups would receive scores according to this criterion.
5.1.2. Number of Good Individuals in a Randomly
Initialized Sample
A good individual or a representative, as it was defined by [22], is a
rule that specifies (has represented) correctly at least all the attributes in one of the terms of the optimal solution to the problem.

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2020

For example, if one of the terms of a problem with d = 5 and
k = 2 is x 1 = 0 / x 4 = 1 (0))1)) possible representatives would
be 0##11, 0##1# and 01110, where # means that the attribute
can take any value. Therefore, this rule does not make mistakes,
but it can be more specific than the optimal rule where only k
attributes are specified. The probabilities of finding a representative were first proposed by [22] for the ternary representation
{0, 1, #}. However, these models were not entirely suitable for
BioHEL, as this system uses a different encoding. Later on, suitable models for the binary domain using the ALKR+GABIL
representation were proposed by [31].
Assuming the usage of the default rule and covering mechanisms, the probability of finding a representative for a binary
problem depends on k and r, as shown in Equation (5). This
function states that the probability of having a good classifier
P(rep) is equal to the probability of having at least one of the
terms in the k-DNF problem represented, and to have a term
represented the rule should express the k relevant attributes.
These models are able to hold with a certain amount of rule
overlap if the rule coverage is uniform. For more details about this
model please see full description presented by [31].
P (rep) = 1 - e 1 - e

2 -k ^l d (1 - p) hk
oo .
1 - ^1 - 2 -khr
r

(5)

In this formula p corresponds to the probability of setting to
1 the values in a GABIL attribute (see Section 3), and ld is the
probability that an attribute appears in the ALKR attribute list.
This value at the same time depends on the user-defined hyperparameter ExpAtts (expected number of attributes) as follows:
1
d 1= ExpAtts
l d = * ExpAtts
.
d 2 ExpAtts
d
Figure 4 shows an example of the landscape of this model
using different values of p. By counting how many representatives are found in a randomly initialized sample of individuals it
is possible to use the formula inversely to determine feasible
pairs of k and r for the given problem.
The individuals for the sample are not generated one by one,
but by chunks of N individuals (for all experiments in this paper N
= 500). After evaluating N rules, it might be possible that we do not
find any representatives. This could happen due to several reasons.
Either the sample is too small and/or the probability of a representative for a particular point is too small as well.To solve these problems
the system increases iteratively the total sample size (generates N
additional samples) until R representatives (hyper-parameter set by
the user) are found. This guarantees that the number of representatives found is not zero while checking the lowest number of individuals as possible. A high value of R will involve checking a bigger
sample size, while a small value would have the opposite effect.
Moreover, we try to generate R representatives using the largest value of p possible, because that would create more general
rules, as shown in Figure 4. However, more general random rules
are more likely to make mistakes. Therefore, when the problem
has a larger k, smaller values of p are needed to generate rules

IEEE Computational Intelligence Magazine - August 2020

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2020