Structural Feature Based Anomaly Detection for Packed Executable Identification - Computational Intelligence in Security for Information Systems - page 287

chromosome is a crossover point or in another words, a linkage group boundary.
Linkage evolving genetic operator (LEGO) [5] is another linkage adaptation strategy
that in order to achieve the linkages, each gene has associated with it two Boolean
flags. These two flags determine whether the gene will link to the genes to its left and
right. The two adjacent genes are assumed to be linked if the appropriate flags are
both set to true. Therefore building blocks are consecutive linked genes on the
chromosome.
Linkage learning is necessary when there are epistatic linkages between variables.
Estimation of distribution algorithms (EDAs) are among the most powerful GAs which
try to find these epistatic linkages through building probabilistic models that summarize
the information of promising solutions in the current population. In another words, by
using probabilistic models these algorithms seek to find linkage between variables of
the problem. In each generation they find as much information as possible about the
variable dependencies from the promising solutions of the population. Knowing this
information, the population of the next generation is created. There are numbers of
estimation of distribution algorithms which their differences are often in the model
building part. Bayesian Networks and marginal product models are examples of the
probabilistic models that have been used by Bayesian Optimization Algorithm (BOA)
[1] and Extended Compact Genetic Algorithm (ECGA) [3]. Although EDAs scale
polynomial in terms of number of fitness evaluations, the probabilistic model building
phase is usually computationally expensive. Perturbation-based method, detect linkage
group by injecting perturbations in the population of individuals and inspecting the
fitness change caused by the perturbation. Gene expression messy genetic algorithm
(gemGA) which uses transcription operator for identifying linkage group is classified in
this category.
Dependency Structure Matrix Genetic Algorithm (DSMGA) [8] is another
approach which models the relationship among variables using Dependency Structure
Matrix (DSM). In DSMGA a clustering method is used for identifying the linkage
groups. In spite of these efforts, none of the algorithms have been claimed to be
stronger that than Hierarchical Bayesian Optimization Algorithms (HBOA) [6] and
[7] which itself in spite of its polynomial scalability in terms of the number of fitness
evaluations, is computationally expensive.
3 Local Optimum Based Linkage Learner: LOLL
The main idea in the proposed approach for identifying the multivariate dependencies
is using local optimums. But how the local optimums can lead us to identification of
the linkage groups?
Local optimums of "Additively Separable problems" have some unique features.
As it is obvious, the global optimum of an additively separable problem is the one that
all of its building blocks are identified. In another words, in the global optimum, all of
the linkage groups of the problem have the highest possible contribution to the overall
fitness. But in local optimum solutions, not all of the building blocks are found and
those partitions or sub-problems of the problem which their optimum values are not
found are occupied by the best competitors of the superior partial solution.