Gene Expression Programming(GEP)

I am trying to implement GEP in common lisp. One of the main points is
the way the chromosome is decoded. Such that given a chromosome:
(+ Q - / b * a a Q b a a b a a b b a a a b)
where Q refers to square root and that + / - * have an arity of 2
while Q has 1. Also a and b are variables. The decoding starts with
the first element as the root, and then proceeds from left to right of
the chromosomes until all the final nodes are variables. Whatever
remains is discarded during fitness testing(but is still considered
part of the chromosome).

http://www.gene-expression-programmi...eOfGEPPrograms

Thus for the chromosome above we would have:
(+ (sqrt (/ a a)) (- b (* (sqrt a) b))).

any suggestions on how to iterate through the chromosome?
Thanks in advance

In article
<8b7250be-1107-44ec-a690-431edc99c1a4@p31g2000prf.googlegroups.com>,
h2s <h2s.search@gmail.com> wrote:

> I am trying to implement GEP in common lisp. One of the main points is
> the way the chromosome is decoded. Such that given a chromosome:
> (+ Q - / b * a a Q b a a b a a b b a a a b)
> where Q refers to square root and that + / - * have an arity of 2
> while Q has 1. Also a and b are variables. The decoding starts with
> the first element as the root, and then proceeds from left to right of
> the chromosomes until all the final nodes are variables. Whatever
> remains is discarded during fitness testing(but is still considered
> part of the chromosome).
>
> http://www.gene-expression-programmi...eOfGEPPrograms
>
> Thus for the chromosome above we would have:
> (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> any suggestions on how to iterate through the chromosome?
> Thanks in advance

In Lisp it is best do iterate from first to last.

--
http://lispm.dyndns.org/

In article <87iqtptu1y.fsf@hubble.informatimago.com>,
pjb@informatimago.com (Pascal J. Bourguignon) wrote:

> h2s <h2s.search@gmail.com> writes:
>
> > I am trying to implement GEP in common lisp. One of the main points is
> > the way the chromosome is decoded. Such that given a chromosome:
> > (+ Q - / b * a a Q b a a b a a b b a a a b)
> > where Q refers to square root and that + / - * have an arity of 2
> > while Q has 1. Also a and b are variables. The decoding starts with
> > the first element as the root, and then proceeds from left to right of
> > the chromosomes until all the final nodes are variables. Whatever
> > remains is discarded during fitness testing(but is still considered
> > part of the chromosome).
> >
> > http://www.gene-expression-programmi...eOfGEPPrograms
> >
> > Thus for the chromosome above we would have:
> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> What rule do you use? In the following, I'll use Polish notation.
>
>
> > any suggestions on how to iterate through the chromosome?
> > Thanks in advance
>
> You don't want to iterate thru it, you want to recurse through it.
>
> (defvar *arities* '((+ . 2) (- . 2) (* . 2) (/ . 2) (Q . 1)))
> (defun build-sexp (chro remainder)
> (let ((arity (or (cdr (assoc (car chro) *arities*)) 0)))
> (case arity
> ((0) (funcall remainder (car chro) (cdr chro)))
> ((1) (build-sexp (cdr chro)
> (lambda (subexpr chro)
> (funcall remainder `(sqrt ,subexpr) chro))))
> ((2) (let ((op (car chro)))
> (build-sexp (cdr chro)
> (lambda (subexpr1 chro)
> (build-sexp chro
> (lambda (subexpr2 chro)
> (funcall remainder
> `(,op ,subexpr1 ,subexpr2) chro)))))))
> (otherwise (error "Arity not considered ~A/~A" (car chro) arity)))))
>
>
> (build-sexp '(+ Q - / b * a a Q b a a b a a b b a a a b)
> (lambda (expr chro) (print expr) (print chro)))
> prints:
> (+ (SQRT (- (/ B (* A A)) (SQRT B))) A)
> (A B A A B B A A A B)

Pascal, that's evil. You are solving every homework. Instructors
will switch away from Lisp.

--
http://lispm.dyndns.org/

h2s <h2s.search@gmail.com> writes:

> I am trying to implement GEP in common lisp. One of the main points is
> the way the chromosome is decoded. Such that given a chromosome:
> (+ Q - / b * a a Q b a a b a a b b a a a b)
> where Q refers to square root and that + / - * have an arity of 2
> while Q has 1. Also a and b are variables. The decoding starts with
> the first element as the root, and then proceeds from left to right of
> the chromosomes until all the final nodes are variables. Whatever
> remains is discarded during fitness testing(but is still considered
> part of the chromosome).
>
> http://www.gene-expression-programmi...eOfGEPPrograms
>
> Thus for the chromosome above we would have:
> (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).

What rule do you use? In the following, I'll use Polish notation.


> any suggestions on how to iterate through the chromosome?
> Thanks in advance

You don't want to iterate thru it, you want to recurse through it.

(defvar *arities* '((+ . 2) (- . 2) (* . 2) (/ . 2) (Q . 1)))
(defun build-sexp (chro remainder)
(let ((arity (or (cdr (assoc (car chro) *arities*)) 0)))
(case arity
((0) (funcall remainder (car chro) (cdr chro)))
((1) (build-sexp (cdr chro)
(lambda (subexpr chro)
(funcall remainder `(sqrt ,subexpr) chro))))
((2) (let ((op (car chro)))
(build-sexp (cdr chro)
(lambda (subexpr1 chro)
(build-sexp chro
(lambda (subexpr2 chro)
(funcall remainder
`(,op ,subexpr1 ,subexpr2) chro)))))))
(otherwise (error "Arity not considered ~A/~A" (car chro) arity)))))


(build-sexp '(+ Q - / b * a a Q b a a b a a b b a a a b)
(lambda (expr chro) (print expr) (print chro)))
prints:
(+ (SQRT (- (/ B (* A A)) (SQRT B))) A)
(A B A A B B A A A B)


--
__Pascal Bourguignon__ http://www.informatimago.com/

"Specifications are for the weak and timid!"

On Aug 25, 3:47*pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
> h2s <h2s.sea...@gmail.com> writes:
> > I am trying to implement GEP in common lisp. One of the main points is
> > the way the chromosome is decoded. Such that given a chromosome:
> > (+ Q - / b * a a Q b a a b a a b b a a a b)
> > *where Q refers to square root and that + / - * *have an arity of 2
> > while Q has 1. Also a and b are variables. The decoding starts with
> > the first element as the root, and then proceeds from left to right of
> > the chromosomes until all the final nodes are variables. Whatever
> > remains is discarded during fitness testing(but is still considered
> > part of the chromosome).
>
> >http://www.gene-expression-programmi...asp#TheArchite...
>
> > *Thus for the chromosome *above we would have:
> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> What rule do you use? *In the following, I'll use Polish notation.
>
> > any suggestions on how to iterate through the chromosome?
> > Thanks in advance
>
> You don't want to iterate thru it, you want to recurse through it.
>
> (defvar *arities* '((+ . 2) (- . 2) (* . 2) (/ . 2) (Q . 1)))
> (defun build-sexp (chro remainder)
> * (let ((arity (or (cdr (assoc (car chro) *arities*)) 0)))
> * * (case arity
> * * * ((0) (funcall remainder (car chro) (cdr chro)))
> * * * ((1) (build-sexp (cdr chro)
> * * * * * * * * * * * *(lambda (subexpr chro)
> * * * * * * * * * * * * *(funcall remainder `(sqrt ,subexpr) chro))))
> * * * ((2) (let ((op (car chro)))
> * * * * * * *(build-sexp (cdr chro)
> * * * * * * * * * * * * *(lambda (subexpr1 chro)
> * * * * * * * * * * * * * *(build-sexp chro
> * * * * * * * * * * * * * * * * * * * *(lambda (subexpr2 chro)
> * * * * * * * * * * * * * * * * * * * * *(funcall remainder
> * * * * * * * * * * * * * * * * * * * * * * * * * `(,op ,subexpr1 ,subexpr2) chro)))))))
> * * * (otherwise (error "Arity not considered ~A/~A" (car chro) arity)))))
>
> (build-sexp '(+ Q - / b * a a Q b a a b a a b b a a a b)
> * * * * * * (lambda (expr chro) (print expr) (print chro)))
> prints:
> (+ (SQRT (- (/ B (* A A)) (SQRT B))) A)
> (A B A A B B A A A B)
>
> --
> __Pascal Bourguignon__ * * * * * * * * * *http://www.informatimago.com/
>
> "Specifications are for the weak and timid!"

First,thanks for your response.Secondly this is not a homework(not
intended to be rude).the inventor of GEP calls the decoding Karva
Language.in it we set the first element as the root of an expression
tree,then we transverse the chromosome from the second element
satisfying the arity of the previous node,taking whatever follows in
the chromosome.as shown in the tree below(taken form Gene Expression
Programming: a New Adaptive Algorithm for Solving Problems by Cândida
Ferreira).
+
/ \
/ \
Q -
| / \
Div b *
/ \ / \
/ \ Q b
a a |
a
There is a freely available C++ and python code,but i would like to
implement it in lisp.
again thanks

h2s <h2s.search@gmail.com> writes:

> On Aug 25, 3:47*pm, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> h2s <h2s.sea...@gmail.com> writes:
>> > I am trying to implement GEP in common lisp. One of the main points is
>> > the way the chromosome is decoded. Such that given a chromosome:
>> > (+ Q - / b * a a Q b a a b a a b b a a a b)
>> > *where Q refers to square root and that + / - * *have an arity of 2
>> > while Q has 1. Also a and b are variables. The decoding starts with
>> > the first element as the root, and then proceeds from left to right of
>> > the chromosomes until all the final nodes are variables. Whatever
>> > remains is discarded during fitness testing(but is still considered
>> > part of the chromosome).
>>
>> >http://www.gene-expression-programmi...asp#TheArchite...
>>
>> > *Thus for the chromosome *above we would have:
>> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>>
>> What rule do you use? *In the following, I'll use Polish notation.
>>
>> > any suggestions on how to iterate through the chromosome?
>> > Thanks in advance
>>
>> You don't want to iterate thru it, you want to recurse through it.
> [...]
>
> First,thanks for your response.Secondly this is not a homework(not
> intended to be rude).the inventor of GEP calls the decoding Karva
> Language.in it we set the first element as the root of an expression
> tree,then we transverse the chromosome from the second element
> satisfying the arity of the previous node,taking whatever follows in
> the chromosome.as shown in the tree below(taken form Gene Expression
> Programming: a New Adaptive Algorithm for Solving Problems by Cândida
> Ferreira).
> +
> / \
> / \
> Q -
> | / \
> Div b *
> / \ / \
> / \ Q b
> a a |
> a

I see, this is a breadth-first walk of the tree. I assume it has
better GP properties than a mere prefix.

There's a solution similar to my build-expr, just changing the order
of some calls.

Otherwise, a normal breadth-first tree building procedure is in order.

--
__Pascal Bourguignon__

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> h2s <h2s.search@gmail.com> writes:
>
>> On Aug 25, 3:47*pm, p...@informatimago.com (Pascal J. Bourguignon)
>> wrote:
>>> h2s <h2s.sea...@gmail.com> writes:
>>> > I am trying to implement GEP in common lisp. One of the main points is
>>> > the way the chromosome is decoded. Such that given a chromosome:
>>> > (+ Q - / b * a a Q b a a b a a b b a a a b)
>>> > *Thus for the chromosome *above we would have:
>>> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>>>
>> +
>> / \
>> / \
>> Q -
>> | / \
>> Div b *
>> / \ / \
>> / \ Q b
>> a a |
>> a
>
> I see, this is a breadth-first walk of the tree. I assume it has
> better GP properties than a mere prefix.
>
> There's a solution similar to my build-expr, just changing the order
> of some calls.
>
> Otherwise, a normal breadth-first tree building procedure is in order.

Like this:

(defun build-breadth-tree (get-node add-child)
"
GET-NODE: A function with no argument that must return two values,
the next node, and its arity.
ADD-CHILD: (add-child node subnode) must attach subnode as the last
child of node.
RETURN: The tree built from the breadth-first-walk returned by GET-NODE.
"
(multiple-value-bind (root arity) (funcall get-node)
(when (plusp arity)
(loop
:with unfilled-nodes = (list (list root arity))
:while unfilled-nodes
:do (loop
:with new-unfilled-nodes = '()
:for (node arity) :in unfilled-nodes
:do (loop
:repeat arity
:do (multiple-value-bind (subnode subarity) (funcall get-node)
(funcall add-child node subnode)
(when (plusp subarity)
(push (list subnode subarity) new-unfilled-nodes))))
:finally (setf unfilled-nodes (nreverse new-unfilled-nodes)))))
root))


(defparameter *arities* '((+ + 2) (- - 2) (* * 2) (/ / 2) (Q sqrt 1)))
(let ((bfw '(+ Q - / b * a a Q b a a b a a b b a a a b)))
(build-breadth-tree
(lambda ()
(let* ((node (pop bfw))
(arity (or (third (assoc node *arities*)) 0))
(fun (second (assoc node *arities*)))) ; try that in scheme! ;-)
(values (if (zerop arity) node (list fun))
arity)))
(lambda (node subnode)
(nconc node (list subnode)))))


--
__Pascal Bourguignon__

On Aug 25, 9:24*pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
> p...@informatimago.com (Pascal J. Bourguignon) writes:
>
>
>
> > h2s <h2s.sea...@gmail.com> writes:
>
> >> On Aug 25, 3:47*pm, p...@informatimago.com (Pascal J. Bourguignon)
> >> wrote:
> >>> h2s <h2s.sea...@gmail.com> writes:
> >>> > I am trying to implement GEP in common lisp. One of the main pointsis
> >>> > the way the chromosome is decoded. Such that given a chromosome:
> >>> > (+ Q - / b * a a Q b a a b a a b b a a a b)
> >>> > *Thus for the chromosome *above we would have:
> >>> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> >> * * * * * * * * * * * * +
> >> * * * * * * * * * * * / * \
> >> * * * * * * * * * * */ * * \
> >> * * * * * * * * * * Q * * * -
> >> * * * * * * * * * * | * * */ *\
> >> * * * * * * * * * * Div * *b * *
> >> * * * * * * * * * * / \ * * * / \
> >> * * * * * * * * * */ * \ * * *Q *b
> >> * * * * * * * * * *a * *a * * |
> >> * * * * * * * * * * * * * * * a
>
> > I see, this is a breadth-first walk of the tree. *I assume it has
> > better GP properties than a mere prefix.
>
> > There's a solution similar to my build-expr, just changing the order
> > of some calls.
>
> > Otherwise, a normal breadth-first tree building procedure is in order.
>
> Like this:
>
> (defun build-breadth-tree (get-node add-child)
> *"
> GET-NODE: *A function with no argument that must return two values,
> * * * * * *the next node, and its arity.
> ADD-CHILD: (add-child node subnode) must attach subnode as the last
> * * * * * *child of node.
> RETURN: * *The tree built from the breadth-first-walk returned by GET-NODE.
> "
> * (multiple-value-bind (root arity) (funcall get-node)
> * * (when (plusp arity)
> * * * (loop
> * * * * *:with *unfilled-nodes = (list (list root arity))
> * * * * *:while unfilled-nodes
> * * * * *:do (loop
> * * * * * * * * :with new-unfilled-nodes = '()
> * * * * * * * * :for (node arity) :in unfilled-nodes
> * * * * * * * * :do (loop
> * * * * * * * * * * * *:repeat arity
> * * * * * * * * * * * *:do (multiple-value-bind (subnode subarity) (funcall get-node)
> * * * * * * * * * * * * * * *(funcall add-child node subnode)
> * * * * * * * * * * * * * * *(when (plusp subarity)
> * * * * * * * * * * * * * * * *(push (list subnode subarity) new-unfilled-nodes))))
> * * * * * * * * :finally (setf unfilled-nodes (nreverse new-unfilled-nodes)))))
> * * root))
>
> (defparameter *arities* '((+ + 2) (- - 2) (* * 2) (/ / 2) (Q sqrt 1)))
> (let ((bfw '(+ Q - / b * a a Q b a a b a a b b a a a b)))
> * (build-breadth-tree
> * *(lambda ()
> * * *(let* ((node * (pop bfw))
> * * * * * * (arity *(or (third (assoc node *arities*)) *0))
> * * * * * * (fun * *(second (assoc node *arities*)))) ; try that in scheme! ;-)
> * * * *(values (if (zerop arity) node (list fun))
> * * * * * * * *arity)))
> * *(lambda (node subnode)
> * * *(nconc node (list subnode)))))
>
> --
> __Pascal Bourguignon__

thanks,i have tested the code on different chromosomes and gives the
expressions as explained in GEP.

h2s schrieb:
> I am trying to implement GEP in common lisp.

It’s a nice training to implement it and can be fun to experiment
with it. Although you didn’t ask for it I just would like to mention
that GEP is not so special as miss Ferreira wants to make us believe.

Especially she often pronouces that GEP is so much better than GP
(Genetic Programming), which is not true.
In fact I am not even sure if GEP usually performs equally well for
most problems, but instead a little bit worse.
She did not understand that she made several mistakes in her measurement
and that’s why she thought in her early trials that she really dis-
covered anything new. GEP is still GP.


André
--

I don’t really understand why complete no ones feel compelled to bad
mouth other peoples work in public. If you disagree with her work and
conclusions write a paper and have it reviewed and published like she
did.