GP GEP Presentation
-
Upload
reyhan-yilmaz -
Category
Documents
-
view
227 -
download
0
Transcript of GP GEP Presentation
-
8/6/2019 GP GEP Presentation
1/31
-
8/6/2019 GP GEP Presentation
2/31
OUTLINE
Evolutionary Algorithms
Genetic Programming (GP)
Gene Expression Programming (GEP)
Applications in the real world problems
-
8/6/2019 GP GEP Presentation
3/31
NP-HARDNESS
Some problems cannot be solved by exact methodsExample: Bandwidth allocation
10 bandwidth ranges, 30 antennas
Supercomputer (109 combinations in 1 s)
Result in roughly 7000 times age of Earth
Approximate results are required
-
8/6/2019 GP GEP Presentation
4/31
EVOLUTIONARY
ALGORITHMS (EA)
Inspired by the process ofnatural evolution
Elements
Chromosome (representation)
Individual (solution)
Fitness
Population
Modifications depend onrepresentation
Initialize population P
Generation g = 0
P' = selection(P)
Recombination (P')
Mutation (P')
Evaluate P
Stoppingcondition
P = P'
g = g + 1
No
Yes
Finish
-
8/6/2019 GP GEP Presentation
5/31
EVOLUTIONARY
ALGORITHMS (EA)
Inspired by the process ofnatural evolution
Elements
Chromosome (representation)
Individual (solution)
Fitness
Population
Modifications depend on
representation
Initialize population P
Generation g = 0
P' = selection(P)
Recombination (P')
Mutation (P')
Evaluate P
Stoppingcondition
P = P'
g = g + 1
No
Yes
Finish
-
8/6/2019 GP GEP Presentation
6/31
GENETIC ALGORITHMS
(GA) (1)
Chromosome is binary string
Solution is a value encoded by the chromosome
Fitness is the performance of the solution
Example:optimize f(x) = x2
Solution - x value
Fitness - y value-2 -1 0 1 2
0.5
1
1.5
2
s1
s2
s3
-
8/6/2019 GP GEP Presentation
7/31
GENETIC ALGORITHMS
(2)
Modifications arestraightforward
Crossover
Mutation
10110011100
00001110001
Parent 1
Parent 2
Crossover point
00001011100
10110110001
Offspring 1
Offspring 2Crossover point
-
8/6/2019 GP GEP Presentation
8/31
GENETIC ALGORITHMS
(2)
Modifications arestraightforward
Crossover
Mutation
10110011100Parent
Offspring
Mutation point
10100011100
-
8/6/2019 GP GEP Presentation
9/31
GA - SUMMARY
Solution is a point in the search space
Chromosome encodes the point as a sequence ofsymbols
-
8/6/2019 GP GEP Presentation
10/31
GENETIC
PROGRAMMING (GP) (1)
Chromosome is aprogram
Program treeTerminals - inputs (T)
Nodes - functions (F)
Solution is the programFitness is itsperformance
a b a
+ sin b a
*
/
f = (a + b) sin(a) a
b
-
8/6/2019 GP GEP Presentation
11/31
GENETIC
PROGRAMMING (2)
Example: data modeling
Solution is a function describing given data set
Fitness is the sum of relative errors of the solution
0 1 2 3 4 5 6
-1
1
2
s1: y = ln(x)
s2: y = 4/x+2.4
-
8/6/2019 GP GEP Presentation
12/31
GENETIC
PROGRAMMING (3)
Modifications areproblematic
Crossover
Mutation
Problems
Syntactic correctness
Tree bloat
a b a
+ b a
* /
sin a b
+
a a
/
Parent 1 Parent 2
Crossover point
a b
+ b a
* /
b
+
a a
/
Offspring 1 Offspring 2
a
a
sin
-
8/6/2019 GP GEP Presentation
13/31
GENETIC
PROGRAMMING (3)
Modifications areproblematic
Crossover
Mutation
Problems
Syntactic correctness
Tree bloat
a b
+
a a
/
Parent
Mutation point
Offspring +
a a
/
+ a
ln b
b
*
-
8/6/2019 GP GEP Presentation
14/31
GENETIC
PROGRAMMING (3)
Modifications areproblematic
Crossover
Mutation
Problems
Syntactic correctness
Tree bloat
a b
+
a a
/
Parent
Mutation point
Offspring +
a a
/
+ a
ln b
b
*
-
8/6/2019 GP GEP Presentation
15/31
GP - SUMMARY
Solution is a program of evaluated performance
Chromosome represents solution as a program tree
Problems
-
8/6/2019 GP GEP Presentation
16/31
Break (10 min)
-
8/6/2019 GP GEP Presentation
17/31
GENE EXPRESSION
PROGRAMMING (GEP) (1)
Chromosome (k-expression) is a sequence of symbolsfrom the set of terminals (T) and functions (F)
Solution (expression tree) is a program decoded fromk-expression
a b
+
c d
/
dcba/+
Expression
TreeK - expression
-
8/6/2019 GP GEP Presentation
18/31
GENE EXPRESSION
PROGRAMMING (2)
Modifications are straightforward
Fixed size sequence of symbols
Karva notation ensures syntactic correctness
-
8/6/2019 GP GEP Presentation
19/31
GENE EXPRESSION
PROGRAMMING (3)
a b
ln
+Expression
Tree
*
*
c/
*d
dcabadbc/baln+ *
Head Tail
Unused part
b
Head -F
andT
Tail - only T
A part of the tail may be
unused
-
8/6/2019 GP GEP Presentation
20/31
GENE EXPRESSION
PROGRAMMING (4)
a b
ln
+Expression
Tree
*
*
c/
*d
dcabadbc/baln+ *
Head Tail
Unused part
b
a
ln
+Expression
Tree
*
*
c/
*b
dcabadbc/+aln+ *
Head Tail
Unused part
a
+
*db
-
8/6/2019 GP GEP Presentation
21/31
GEP - SUMMARY
Combines properties of GA and GP
Fixed size sequence of symbols prevents tree bloat
Karva notation ensures solution correctness
Offers intensive exploration of the search space
Interesting for epistatic problems
-
8/6/2019 GP GEP Presentation
22/31
INTRUSION DETECTION
WITH GEP
Problem definition
Fitness calculation
Results and comparison with regular approach
-
8/6/2019 GP GEP Presentation
23/31
PROBLEM DEFINITION
Network traffic is described with a set of parameters
e.g packets/s, bytes/s, etc.
We search for a classification function g(x)
g(x) > 1 during attack
g(x) < 1 during regular traffic
-
8/6/2019 GP GEP Presentation
24/31
FITNESS CALCULATION
(1)
Input: time series of monitored parameters
E.g. two parameters p and b and time windoww = 2 give s = [pt0, pt1, pt2,bt0,bt1,bt2]
Three parameters taken from traffic clustering
Size, Number and Ratio (Capacity/Number)
Seven values ofw = {5, 10 - 60}
-
8/6/2019 GP GEP Presentation
25/31
FITNESS CALCULATION
(2)
Fitness is the classification performance
Sensitivity
Specificity
Learning set composed of time series samples
Training set
Testing set
-
8/6/2019 GP GEP Presentation
26/31
RESULTS
Comparison with regular approach (thresholding)
-
8/6/2019 GP GEP Presentation
27/31
FUNCTION FINDING
WITH GEP
Problem definition
Fitness calculation
Results
-
8/6/2019 GP GEP Presentation
28/31
PROBLEM / FITNESS
Problem: having set of 3-d points P find a functionfitting these points
Fitness: sum of relative errors of a given function
concerning P
-
8/6/2019 GP GEP Presentation
29/31
RESULTS
Mexican Hat
f(x, y) = 1 (a2 + b2) ea2+b2
2
Found
f(x, y) =
((1 + sin(sin(x ln(y) + 2)) + sin(sin(2sin(y2
))))
(ey2 sin(1 sin(x + y)))) +sin(1)
eeyx+1
-
8/6/2019 GP GEP Presentation
30/31
SUMMARY
Evolution of programs is an interesting and useful
approach to problem solving
Challenging issues
Search guidance
Solution structure
-
8/6/2019 GP GEP Presentation
31/31
THANK YOU
Questions ?